题解 P6617 【查找 Search】

FZzzz · 2020-06-15 10:23:15 · 题解

比较显然地：定义一个位置的前驱为这个位置之前第一个与这个位置加起来等于 w 的位置，没有则为 0，则答案为区间内所有数前驱的最大值是否大于等于 l。

然后发现这样的话修改就炸了，因为有很多数的前驱会改变。

然后有一个比较巧妙的转化，就是如果一个数的前驱比它前面第一个与他相同的位置要小，则我们直接把这个位置的前驱设为零。可以发现这样是对的。

这个大概是我赛时的思路，然后我就极其 naive 地以为这样也没法直接修改……

事实上可以直接修改。发现新定义的前驱会改变的位置最多只有五个：这个位置，这个位置原来后面第一个与他相同的位置，这个位置原来后面第一个与他相加得 w 的位置，这个位置后来后面第一个与他相同的位置，这个位置后来后面第一个与他相加得 w 的位置。

直接用 set 维护每个值出现的位置，然后在线段树上修改即可。

#include<algorithm>
#include<set>
#include<vector>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=5e5+5;
int n,m,w,a[maxn];
set<int> s[maxn];
typedef set<int>::iterator iter;
struct node{
    int l,r;
    node* ch[2];
    int mx;
    void pushup(){
        mx=max(ch[0]->mx,ch[1]->mx);
    }
    node(int l,int r):l(l),r(r),mx(0){
        if(l<r){
            int mid=l+(r-l)/2;
            ch[0]=new node(l,mid);
            ch[1]=new node(mid+1,r);
            pushup();
        }
    }
    void modify(int x,int k){
        if(l==r) mx=k;
        else{
            if(x<=ch[0]->r) ch[0]->modify(x,k);
            else ch[1]->modify(x,k);
            pushup();
        }
    }
    int query(int ql,int qr){
        if(ql<=l&&qr>=r) return mx;
        else{
            int ans=0;
            if(ql<=ch[0]->r) ans=max(ans,ch[0]->query(ql,qr));
            if(qr>=ch[1]->l) ans=max(ans,ch[1]->query(ql,qr));
            return ans;
        }
    }
}*rt;
int pre(int x){
    iter it1=s[a[x]].lower_bound(x),it2=s[w-a[x]].lower_bound(x);
    if(it2==s[w-a[x]].begin()) return 0;
    else if(it1==s[a[x]].begin()) return *--it2;
    else if(*--it1>*--it2) return 0;
    else return *it2;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    m=readint();
    w=readint();
    for(int i=1;i<=n;i++) a[i]=readint();
    rt=new node(1,n);
    for(int i=1;i<=n;i++){
        rt->modify(i,pre(i));
        s[a[i]].insert(i);
    }
    int cnt=0;
    while(m--){
        int op=readint();
        if(op==1){
            int x,k;
            x=readint();
            k=readint();
            vector<int> res;
            iter it=s[a[x]].upper_bound(x);
            if(it!=s[a[x]].end()) res.push_back(*it);
            it=s[w-a[x]].upper_bound(x);
            if(it!=s[w-a[x]].end()) res.push_back(*it);
            s[a[x]].erase(x);
            s[a[x]=k].insert(x);
            res.push_back(x);
            it=s[a[x]].upper_bound(x);
            if(it!=s[a[x]].end()) res.push_back(*it);
            it=s[w-a[x]].upper_bound(x);
            if(it!=s[w-a[x]].end()) res.push_back(*it);
            for(int i=0;i<(int)res.size();i++) rt->modify(res[i],pre(res[i]));
        }
        else{
            int l,r;
            l=readint()^cnt;
            r=readint()^cnt;
            if(rt->query(l,r)>=l){
                cnt++;
                printf("Yes\n");
            }
            else printf("No\n");
        }
    }
    return 0;
}