こっちの方が素直。
https://yukicoder.me/problems/no/1290
問題
整数列A,Bといくつかの区間が与えられる。
Aは初期状態で0である。
与えられた区間のいずれかを選択し、その区間を[L,R]としたとき、整数Kを選んでL≦i≦Rの範囲に対し、A[i] += K*(-1)^(i-L)を加算する、という処理を繰り返すとする。
AをBに一致させられるか。
左端が一致する複数の区間があった場合、分離して左端をユニークにしよう。
[L,R]と[L,R']がありR<R'なら、この2つの区間は実質[L,R]と[R+1,R']に分離できる。
この処理はマージテクを使うと高速に行うことができる。
各区間の左端がユニークになったら、あとは端から値を決めていくだけ。
int N,M; ll B[101010]; set<int> R[2020202]; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<ll,20> bt; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) cin>>B[i]; FOR(i,M) { cin>>x>>y; R[x-1].insert(y); } FOR(i,N) { if(R[i].size()) { x=*R[i].begin(); R[i].erase(R[i].begin()); if(R[x].size()<R[i].size()) swap(R[i],R[x]); FORR(v,R[i]) R[x].insert(v); R[i].clear(); ll v=bt(i); if(i%2==0) { ll d=B[i]-v; bt.add(i,d); bt.add(x,-d); } else { ll d=B[i]-(-v); bt.add(i,-d); bt.add(x,d); } } if(i%2==0&&bt(i)!=B[i]) { cout<<"NO"<<endl; return; } if(i%2==1&&bt(i)!=-B[i]) { cout<<"NO"<<endl; return; } } cout<<"YES"<<endl; }
まとめ
★下がった?