CF551E题解 BY 蒟蒻

reyik · 2018-12-09 19:06:02 · 题解

开门见山：

分块。啊！！

然后对每一个块进行一次排序

对每个块记录排序后的元素（及其下标）。

每一次修改，整块的直接打标记。对于两边没在块中的，没办法，蒟蒻只会暴力。。。（还是太弱）

对于查询，我们很快就能联想到二分查找

我们在每一个块中进行二分查找

好像完了

时间复杂度O(Qnlog(n))

蒟蒻奉献代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define Rint regiter int
#define Temp template<typename T>
using namespace std;
Temp inline void read(T &x) {
    x=0;
    T w=1,ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=w;
}
const int maxn=5e5+10;
typedef long long ll;
struct node {
    ll x;
    int id,loc;
    bool operator < ( const node& a ) const {
        if ( id == a.id && x == a.x ) return loc < a.loc;
        if ( id == a.id ) return x < a.x;
        return id < a.id;
    }
} p[maxn];
int n,q;
ll add[maxn];
int m,cnt=0,low[maxn],high[maxn];
int main() {
    read(n);
    read(q);
    m=sqrt(n)+1;
    cnt=0;
    memset(add,0,sizeof(add));
    memset(low,-1,sizeof(low));
    memset(high,-1,sizeof(high));
    for (int i=0; i<n; ++i) {
        read(p[i].x);
        p[i].id=i/m;
        p[i].loc=i;
        cnt=max(cnt,i/m);
        if(low[cnt]==-1) low[cnt]=i;
        high[cnt]=max(high[cnt],i);
    }
    cnt++;
    sort(p,p+n);//先总排序
    while(q--) {
        int kind;
        read(kind);
        if(kind==1) {
            int l,r;
            int x1;
            read(l);
            read(r);
            read(x1);
            l--,r--;
            for (int i=0; i<cnt; ++i) {
                if((l<=low[i])&&(r>=high[i])) add[i]+=x1;
                else if(low[i]>r||high[i]<l) continue;
                else {
                    for (int j=low[i]; j<=high[i]; ++j) {
                        if(p[j].loc>=l && p[j].loc<=r) {
                            p[j].x+=x1;
                        }
                    }
                    sort(p+low[i],p+high[i]+1);//在每一次修改后排序维护
                }
            }
        } else {
            int x1;
            read(x1);
            int left=maxn,right=-1;
            for (int i=0; i<cnt; ++i) {
                ll tmp=x1-add[i];
                int l=low[i],r=high[i],mid;
                while(l!=r) {//二分最左边
                    mid=(l+r+1)>>1;
                    if(p[mid].x>tmp) r=mid-1;
                    else l=mid;
                }
                if(p[l].x==tmp) right=max(right,p[l].loc);
                l=low[i],r=high[i];
                while(l!=r) {//二分最右边
                    mid=l+r>>1;
                    if(p[mid].x<tmp) l=mid+1;
                    else r=mid;
                }
                if(p[l].x==tmp) left=min(left,p[l].loc);
            }
            if(right==-1) puts("-1");
            else printf("%d\n",right-left);
        }
    }
    return 0;
}