#4017.コピー&ペースト(copypasste)

タイトルの説明
テキストエディタの最も重要な機能は、コピー&貼り付けです.JOI社は現在、非常に高速にコピー&貼り付けが可能なテキストエディタを開発しており、JOI社の優れたプログラム猿として、コピー&貼り付け機能のテストという核心的な仕事を担っています.JOI社全体の運命はあなたにかかっているので、どうしても正確で高速なプログラムを書いてこの仕事を完成したいと思っています.
具体的なやり方は以下の通りです.ファイルの内容は文字列Sであり、N回コピー&ペースト操作を行い、i回目は位置Aiと位置Biの間のすべての文字をコピーし、位置Ciにペーストする.ここで、位置xは文字列のx番目の文字の後ろの位置(位置0は文字列の先頭を表す)、例えば文字列「copypasste」の位置6は文字「a」と文字「s」の間の位置、位置9は「e」の後ろの位置(すなわち文字列の末尾)を表す.ただし、操作後の文字列の長さがMを超えると、超えた部分は削除され、長さMの接頭辞のみが保持されます.
あなたの任務はプログラムを書いて、N回の操作後の文字列の前のK文字を出力することです.
入力フォーマット
1行目の2つのスペースで区切られた正の整数KとMは、最終出力の文字数と文字列長の上限を表します.
2行目の文字列Sは、初期の文字列を表す.
3行目の整数Nは、操作の回数を表す.
次にN行目、i行目は3つのスペースで区切られた整数Ai,Bi,Ciを含み、i回目の操作で位置AiからBiまでの文字列をコピーし、位置Ciに貼り付けることを示す.
出力フォーマット
最終的な文字列の長さKを表す接頭辞の行をKとする文字列を出力します.
サンプルサンプル入力
2 18 copypaste 4 3 6 8 1 5 2 4 12 1 17 18 0
サンプル出力
ac
データ範囲とヒント
【様式解釈】
初期の文字列は「copypasste」です.
1回目の操作で位置3から位置6までの文字列「ypa」をコピーし、位置8を挿入して文字列「copypassypae」を得る
2回目の操作で位置1から位置5までの文字列「opyp」をコピーし、位置2を挿入して文字列「coopyppasypae」を得る
3回目の操作で位置4から位置12までの文字列「yppypast」をコピーし、位置1を挿入して文字列「cyppypastoopyppasypae」を得、長さがM=18を超えたため、超えた部分を削除して「cyppypastoopyppay」を得る
4回目の操作で位置17から位置18までの文字列「a」をコピーし、位置0を挿入して文字列「acyppypastoopyppa」を得、18を超える部分を削除して「acyppypastoopypp」を得る
最後の出力長が2のプレフィックス「ac」が答えです.
【データ範囲と約定】
40%のデータに対して、N,M<=2000
100%のデータについて:1<=K<=200,1<=M<=10^9
Sの各文字は小文字(‘a’~’z’),K<=|S|<=min(M,210^5)である.
1<=N<=210^5、i回目の操作前の文字列長をLiとすると、0<=Ai
ソース
JOI camp 2015問題解:kが小さいことに気づいたので、時間の複雑さはO(nk)であるべきだと大胆に推測することができます.同時に最後に生成されたすべての文字は初期文字列から来ており、f[i][j]が最終文字列のj番目の文字がiステップ後の文字列を表す位置を逆に推定できることが分かる.これで3種類に分けて討論し、押し返すだけだ.

#include
#include
#include
#include
#include
#define N 200005
using namespace std;
int f[N][205],n,k,m;
string str;
struct node
{
	int a,b,c;
}op[N];
int main()
{
    cin>>k>>m;
	cin>>str;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>op[i].a>>op[i].b>>op[i].c;
	}
	for(int j=1;j<=k;j++){
		f[n][j]=j;
		for(int i=n;i>=1;i--){
			int a=op[i].a+1,b=op[i].b,c=op[i].c+1;
			if(c>f[i][j]){f[i-1][j]=f[i][j];continue;}
			if(c+(b-a)<f[i][j]){f[i-1][j]=f[i][j]-(b-a+1);continue;}
			f[i-1][j]=a+f[i][j]-c;
		}
		cout<<str[f[0][j]-1];
	}cout<<endl;
	return 0;
}