題意：給出一個數列，要求支持以下兩種操作，1）給某區間內的所有數都加上x，2）輸出數列中等于y的兩個數的最大距離。
比賽的時候沒想到這是分塊（花式暴力。。），以為是線段書啥的，然后不會。。賽后聽說是分塊，其實思路一下就想到了（以前照書抄過一個分塊題）。。。。然而第一次寫的時候腦殘完全寫錯了，發現的時候汗啊。。全刪了重寫，又寫了一個小時左右，wa了兩次，修正了兩個bug，過了。。。分成若干塊，如果改變的區間完全包含一個塊，那就直接給總的val加x，不完全包含就o(n)直接處理，查詢的時候是二分，其實這個題還是比較簡單的分塊，因為查詢沒有區間問題，就是從頭到尾，否則查詢也比較麻煩。
#include<iostream> #include<map> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<functional> #define pb push_back using namespace std; typedef long long ll; const int maxv=5e5+40; const int sz=1000; struct Num{ll o,v;bool operator < (const Num &C)const{if(v!=C.v) return v<C.v;else return o<C.o;} }; vector<Num> bucket[1000]; ll a[maxv]; ll val[maxv]; int n,q; void update(int l,int r,ll x){if(l/sz==r/sz){for(int i=l;i<=r;i++) a[i]+=x;bucket[l/sz].clear();for(int i=l/sz*sz;i<l/sz*sz+sz;i++) bucket[l/sz].pb((Num){i,a[i]});sort(bucket[l/sz].begin(),bucket[l/sz].end());}else{for(int i=l/sz+1;i<r/sz;i++) val[i]+=x;update(l,l/sz*sz+sz-1,x);update(r/sz*sz,r,x);}return; } bool cmp(Num a,Num b){return a.v<b.v; } int quaryl(ll y){for(int i=0;i<=n/sz;i++){Num tar;tar.v=y-val[i];vector<Num>::iterator it=lower_bound(bucket[i].begin(),bucket[i].end(),tar,cmp);if(it!=bucket[i].end()&&(*it).v==tar.v){return (*it).o;}}return -1; } int queryr(ll y){for(int i=n/sz;i>=0;i--){Num tar;tar.v=y-val[i];vector<Num>::iterator it=upper_bound(bucket[i].begin(),bucket[i].end(),tar,cmp);if(it!=bucket[i].begin()&&(*(it-1)).v==tar.v){return (*(it-1)).o;}}return -1; } int main(){////freopen("/home/files/CppFiles/in","r",stdin);cin>>n>>q;for(int i=0;i<n;i++){scanf("%I64d",&a[i]);bucket[i/sz].pb((Num){i,a[i]});}for(int i=0;i<=n/sz;i++) sort(bucket[i].begin(),bucket[i].end());while(q--){int type;scanf("%d",&type);if(type==1){int l,r,x;scanf("%d%d%d",&l,&r,&x);update(l-1,r-1,x);}else{int y;scanf("%d",&y);int l=quaryl(y);if(l!=-1){printf("%d\n",queryr(y)-l);}else{puts("-1");}}}return 0; }
設A的平方等于E、?
