[Codeforces] 551E. GukiZ and GukiZiana

題目連結:http://codeforces.com/problemset/problem/551/E

---

把序列分成$\sqrt{N}$塊後，每次操作就變得很簡單了，修改時如果那塊完整被覆蓋就直接在懶標記上修改，而如果沒有就把那塊重新建置一次；詢問時就先看一下懶標記，再查詢即可。複雜度$O(Q \sqrt{N})$

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second
typedef long long lld;
const int K = 710;
const int N = 500000 + 5;

lld arr[N], flag[K];
unordered_map<lld, PII> blk[K];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, q; cin>>n>>q;
	for(int i=0;i<n;i++) cin>>arr[i];
	const int k = ceil(sqrt(n));
	for(int i=0;i<n;i+=k){
		for(int j=i;j<min(n, i+k);j++){
			if(blk[i/k].find(arr[j])==blk[i/k].end()) blk[i/k][arr[j]].FF = j;
			blk[i/k][arr[j]].SS = j;
		}
	}
	while(q--){
		int tp; cin>>tp;
		if(tp==1){
			int l, r; lld v; cin>>l>>r>>v;
			l--;
			const PII ID = {l/k, (r-1)/k};
			blk[ID.FF].clear();
			for(int i=ID.FF*k;i<min((ID.FF+1)*k, n);i++){
				if(l <= i and i < r) arr[i]+=v;
				if(blk[ID.FF].find(arr[i])==blk[ID.FF].end()) blk[ID.FF][arr[i]].FF = i;
				blk[ID.FF][arr[i]].SS = i;
			}
			if(ID.FF != ID.SS){
				blk[ID.SS].clear();
				for(int i=ID.SS*k;i<min((ID.SS+1)*k, n);i++){
					if(l <= i and i < r) arr[i]+=v;
					if(blk[ID.SS].find(arr[i])==blk[ID.SS].end()) blk[ID.SS][arr[i]].FF = i;
					blk[ID.SS][arr[i]].SS = i;
				}
			}
			for(int i=(ID.FF+1);i<ID.SS;i++) flag[i]+=v;
		}else if(tp==2){
			lld x; cin>>x;
			int l=n, r=-1;
			for(int i=0;i<n;i+=k){
				if(blk[i/k].find(x-flag[i/k]) == blk[i/k].end()) continue;
				l = min(l, blk[i/k][x-flag[i/k]].FF);
				r = max(r, blk[i/k][x-flag[i/k]].SS);
			}
			cout<<max(r-l, -1)<<'\n';
		}
	}
	return 0;
}