yukicoder : No.1386 Range add Simulation

うーむややこしい。
https://yukicoder.me/problems/no/1386

問題

整数列Aが与えられる。
Aは、区間に対し2次式で定義される値を足す、という処理をQ回分行った形で与えられる。

今、全要素0である整数列Bがある。
これに以下の処理を行い、BをAに一致させよ。

• 任意要素をインクリメントまたはデクリメントする。
• ある要素を、隣接要素に足しこむor引く。

解法

2次式なので3回階差を取ると、0でない要素は定数個になる。
そこで、各クエリを3回階差を取った場合を考え、全クエリの和を求めよう。
最後に3回累積和を取る。

int N,Q;
ll V[101010];
ll A[101010];
ll B[101010];


vector<vector<int>> R;

void dfs(int cur,ll v) {
	if(v==0) return;
	if(v/2) {
		dfs(cur,v/2);
		B[cur]*=2;
		R.push_back({3,cur,cur});
	}
	if(v%2) {
		if(v>0) R.push_back({1,cur}), B[cur]++;
		else R.push_back({2,cur}), B[cur]--;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>x>>y;
		if(x==1) {
			if(y==1) {
				V[1]++;
				V[2]+=3;
				V[3]+=2;
			}
			else if(y==2) {
				V[2]++;
				V[3]+=2;
			}
			else {
				V[y]++;
				V[y+1]++;
			}
			//for(j=y;j<=N;j++) A[j]+=1LL*(j-y+1)*(j-y+1);
		}
		else {
			V[1]+=1LL*y*y;
			V[2]-=2*y-1;
			V[3]+=2;
			V[y+2]--;
			V[y+3]--;
			//for(j=1;j<=y;j++) A[j]+=1LL*(j-y+1)*(j-y+1);
		}
	}
	for(i=1;i<=N;i++) dfs(i,V[i]);
	for(i=3;i<N;i++) R.push_back({3,i+1,i}), B[i+1]+=B[i];
	for(i=2;i<N;i++) R.push_back({3,i+1,i}), B[i+1]+=B[i];
	for(i=1;i<N;i++) R.push_back({3,i+1,i}), B[i+1]+=B[i];
	cout<<R.size()<<endl;
	FORR(r,R) {
		FORR(v,r) cout<<v<<" ";
		cout<<endl;
	}
	
	
}

まとめ

階差を取ることは思いついても、そこから詰め切るのがめんどい。