不认识 题解

``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000010; typedef long long ll; ll n,q,lstans,idx,l,r,sum[maxn*4],rv[maxn*4],lzy[maxn*4]; void pushdown(ll o,ll l,ll r) { lzy[o<<1]=lzy[o<<1|1]=lzy[o]; rv[o<<1]=rv[o<<1|1]=lzy[o]; ll mid=(l+r)>>1; sum[o<<1]=(mid-l+1)*lzy[o]; sum[o<<1|1]=(r-(mid+1)+1)*lzy[o]; lzy[o]=0; } void Set(ll o,ll l,ll r,ll sl,ll sr,ll v) { if(sl>r||sr<l)return; if(sl<=l&&r<=sr){lzy[o]=v;sum[o]=(r-l+1)*v;rv[o]=v;return;} ll mid=(l+r)>>1; if(lzy[o])pushdown(o,l,r); Set(o<<1,l,mid,sl,sr,v); Set(o<<1|1,mid+1,r,sl,sr,v); sum[o]=sum[o<<1]+sum[o<<1|1]; rv[o]=rv[o<<1|1]; } ll Query(ll o,ll l,ll r,ll ql,ll qr) { if(ql>r||qr<l)return 0; if(ql<=l&&r<=qr)return sum[o]; ll mid=(l+r)>>1; if(lzy[o])pushdown(o,l,r); return Query(o<<1,l,mid,ql,qr)+Query(o<<1|1,mid+1,r,ql,qr); } ll Find(ll o,ll l,ll r,ll v) { if(l==r)return l; if(lzy[o])pushdown(o,l,r); ll mid=(l+r)>>1; if(rv[o<<1]>=v)return Find(o<<1,l,mid,v); return Find(o<<1|1,mid+1,r,v); } int main() { scanf("%lld%lld",&n,&q); for(ll i=1;i<=n;i++)Set(1,1,n,i,i,i); while(q--) { scanf("%lld%lld",&l,&r); l^=lstans;r^=lstans; idx=Find(1,1,n,r);//the last number index witch <=r idx--; if(idx>=l)lstans=r*(idx-l+1)-Query(1,1,n,l,idx); else lstans=0; printf("%lld\n",lstans); if(idx>=l)Set(1,1,n,l,idx,r); } return 0; } ```