题目链接:链接
本人解答代码如下,但是是错误的,请各位帮个忙。
#include<bits/stdc++.h>
namespace fast_IO
{
#define Getchar() p1==p2 and (p2=(p1=Inf)+fread(Inf,1,1<<21,stdin),p1==p2)?EOF:*p1++
#define Putchar(c) p3==p4 and (fwrite(Ouf,1,1<<21,stdout),p3=Ouf),*p3++=c
char Inf[1<<21],Ouf[1<<21],*p1,*p2,*p3=Ouf,*p4=Ouf+(1<<21);
inline void read(int &x,char c=Getchar())
{
bool f=c!=45;
x=0;
while(c<48 or c>57) c=Getchar(),f&=c!=45;
while(c>=48 and c<=57) x=(x<<3)+(x<<1)+(c^48),c=Getchar();
x=f?x:-x;
}
inline void write(int x)
{
if(x<0) Putchar(45),x=-x;
if(x>=10) write(x/10),x%=10;
Putchar(x^48);
}
inline void write(std::string st)
{
for(int i=0;i<st.size();i++) Putchar(st[i]);
}
};
using namespace fast_IO;
int n,m,w,a[500010],pre[500010],ed[500010];
std::unordered_map< int,std::set<int> > mp;
struct node
{
int mpre;
node *lc,*rc;
inline void pushup()
{
mpre=std::max(lc->mpre,rc->mpre);
}
};
class seg_tree
{
#define ls l,mid
#define rs mid+1,r
private:
node *root;
inline node *build(int l,int r)
{
node *rt=new node;
if(l==r) rt->mpre=pre[l];
else
{
int mid=(l+r)/2;
rt->lc=build(ls),rt->rc=build(rs),rt->pushup();
}
return rt;
}
inline void fix(node *rt,const int &pos,const int &val,int l,int r)
{
if(l==r)
{
rt->mpre=val;
return;
}
int mid=(l+r)/2;
if(pos<=mid) fix(rt->lc,pos,val,ls);
else fix(rt->rc,pos,val,rs);
rt->pushup();
}
inline int ask(node *rt,const int &L,const int &R,int l,int r)
{
if(L<=l && r<=R) return rt->mpre;
int mid=(l+r)/2,ret=0;
if(L<=mid) ret=std::max(ret,ask(rt->lc,L,R,ls));
if(R>mid) ret=std::max(ret,ask(rt->rc,L,R,rs));
return ret;
}
public:
inline void build()
{
root=build(1,n);
}
inline void fix(const int &pos,const int &val)
{
fix(root,pos,val,1,n);
}
inline int ask(const int &L,const int &R)
{
return ask(root,L,R,1,n);
}
};
seg_tree tree;
std::vector< std::pair<int,int> > v;
inline void addget(const int &val,const int &it)
{
v.push_back(std::make_pair(val,it));
}
inline void getpre(const int &val,const int &it)
{
if(mp[w-val].empty())
{
pre[it]=-1,tree.fix(it,pre[it]);
return;
}
if(val*2==w)
{
std::set<int>::iterator it2=mp[val].find(it);
if(it2==mp[val].begin()) pre[it]=-1,tree.fix(it,pre[it]);
else it2--,pre[it]=*it2,tree.fix(it,pre[it]);
return;
}
std::set<int>::iterator it2=mp[w-val].lower_bound(it),it3=mp[val].find(it);
if(it2==mp[w-val].begin())
{
pre[it]=-1,tree.fix(it,pre[it]);
return;
}
it2--,pre[it]=*it2,tree.fix(it,pre[it]);
if(it3!=mp[val].begin())
{
it3--;
if(pre[*it3]==pre[it]) pre[it]=-1,tree.fix(it,pre[it]);
}
}
inline void deladd()
{
for(int i=0;i<v.size();i++) getpre(v[i].first,v[i].second);
v.clear();
}
int main()
{
freopen("example.in","r",stdin);
freopen("example.out","w",stdout);
read(n),read(m),read(w);
for(int i=1;i<=n;i++) read(a[i]);
std::set<int>::iterator it1,it2,it3;
for(int i=1,prev;i<=n;i++)
{
if(!mp[w-a[i]].size()) pre[i]=-1;
else
{
prev=*(--mp[w-a[i]].end());
if(ed[prev]) pre[i]=-1;
else pre[i]=prev,ed[prev]=1;
}
mp[a[i]].insert(i);
}
tree.build();
for(int i=1,op,l,r,ans=0;i<=m;i++)
{
read(op),read(l),read(r);
if(op==1)
{
it1=mp[a[l]].find(l),it2=mp[w-a[l]].lower_bound(l);
if(it2!=mp[w-a[l]].end()) addget(w-a[l],*it2);
if(it1!=mp[a[l]].end())
{
it1++;
if(it1!=mp[a[l]].end()) addget(a[l],*it1);
}
mp[a[l]].erase(l),mp[r].insert(l),a[l]=r;
it1=mp[a[l]].find(l),it2=mp[w-a[l]].lower_bound(l),addget(a[l],*it1);
if(it2!=mp[w-a[l]].end()) addget(w-a[l],*it2);
if(it1!=mp[a[l]].end())
{
it1++;
if(it1!=mp[a[l]].end()) addget(a[l],*it1);
}
deladd();
}else
{
l^=ans,r^=ans;
if(tree.ask(l,r)>=l) write("Yes\n"),ans++;
else write("No\n");
}
// debug();
}
fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
return 0;
}