[CF 551E] GukiZ and GukiZiana

作法：

將整個序列切成$\sqrt{n}$塊，我們先看每一塊中必須支援什麼操作才有辦法處理題目的要求。對於把原數列的某個區間同加一個數的操作，把他拆成由好幾個已經切好的好幾塊組成，對於其中一塊來說，可能要加的區間完整覆蓋他，或是沒有完整覆蓋，並且滿足沒有完整覆蓋的塊頂多只有$2$個。至於題目的詢問，只要能夠在每塊中查詢某個數第一次和最後一次出現的位置就可以了，枚舉$\sqrt{n}$塊即可找出答案。因此對於每一塊，我們可以用一個 map<long long,vector<int>> ，代表某個數值出現的所有位置（因為可能一個數被加超過 int），還有一個$tag$值代表這裡面所有數都應該要增加$tag$，也就是當查詢的值為$x$時要去 map 的 key 值為$x-tag$的 vector 裡面找。而當我們要把一塊中的部份幾個數同加一個值時，就直接把那塊砍掉重建就好了，因為每次操作至多發生兩次這樣的事，所以複雜度不會爛掉。

但這樣傳上去TLE了，我後來加了個優化才過：因為詢問的數頂多到$10^9$，而且每次對一個區間加的數都是非負的，所以當某個位子的數超過$10^9$時他就再也不可能被詢問到了，因此可以在重建某一塊時直接忽略掉那個位子的數。另外對於每一塊也一樣，如果有一天某一塊的$tag$值超過$10^9$，那麼那一塊就廢掉了，之後重建就可以不用裡他了。這樣就可以把所有 long long 都改回 int ，因為測資很大，所以這樣就可以快很多了。

code :

#include<bits/stdc++.h>
#define INF 1000000000
#define F first
#define S second
using namespace std;
const int maxn=500000+10,maxsq=2000 ;
bool exc[maxn] ;
 
struct P
{
    map<int,vector<int>> mp ;
    int l,r,tag ;
    bool exc ;
    P(){tag=0 ; exc=0 ;}
    void build() ;
    void add(int L,int R,int val) ;
    void query(int &L,int &R,int val)
    {
        auto it=mp.find(val-tag) ;
        if(it==mp.end()){L=R=-1 ; return ;}
        L=maxn , R=-1 ;
        for(auto i : it->S) L=min(L,i) , R=max(R,i) ;
    }
};
 
int a[maxn] ;
void P::build()
{
    mp.clear() ;
    for(int i=l;i<=r;i++) if(!::exc[i])
    {
        if(INF-tag<a[i]){::exc[i]=1 ; continue ;}
        a[i]+=tag ;
        mp[a[i]].push_back(i) ;
    }
    tag=0 ;
}
void P::add(int L,int R,int val)
{
    if(this->exc) return ;
    if(l==L && r==R)
    {
        tag+=val ;
        if(tag>INF) this->exc=1 ;
        return ;
    }
    for(int i=L;i<=R;i++) if(!::exc[i])
        a[i]+=val ;
    this->build() ;
}
 
P p[maxsq] ;
main()
{
    int n,Q ; scanf("%d%d",&n,&Q) ;
    for(int i=0;i<n;i++) scanf("%d",&a[i]) ;
    int sq=int(sqrt(n+0.5)) ;
    for(int i=0;i<n;i+=sq)
    {
        p[i/sq].l=i , p[i/sq].r=min(i+sq-1,n-1) ;
        p[i/sq].build() ;
    }
    while(Q--)
    {
        int op ; scanf("%d",&op) ;
        if(op==1)
        {
            int x,y,val ; scanf("%d%d%d",&x,&y,&val) ;
            x-- ; y-- ;
            int lb=x/sq , rb=y/sq ;
            for(int i=lb;i<=rb;i++)
                p[i].add(max(i*sq,x),min(i*sq+sq-1,y),val) ;
        }
        else
        {
            int x ; scanf("%d",&x) ;
            int ansl=-1 , ansr=-1 ;
            for(int i=0,j=0;j<n;i++,j+=sq)
            {
                int L,R ; p[i].query(L,R,x) ;
                if(L!=-1){ansl=L ; break ;}
            }
            if(ansl==-1){printf("-1\n") ; continue ;}
            for(int i=(n-1)/sq;i>=0;i--)
            {
                int L,R ; p[i].query(L,R,x) ;
                if(R!=-1){ansr=R ; break ;}
            }
            printf("%d\n",ansr-ansl) ;
        }
    }
}