打表找规律+动态开点线段树/平衡树/set/OVT

之前luogu比赛的一题

当时打表打出了规律

然后写数据结构维护写挂了

于是今天就重新写了下，顺便加深了动态开点线段树的理解

#include <bits/stdc++.h>
#define il inline
#define Max 5000005
#define ll long long
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
int ls[Max],rs[Max],tg[Max],lx[Max],rx[Max],rt,n,m;
char In[Max],*ss=In,*tt=In;
ll t[Max],cnt;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
il int calc(int x)
{
    int nw=x%4;
    if(!nw) return x<<1;
    if(nw==1) return 3;
    if(nw==2) return (x+1)<<1;
    else return 1;
}
il void pushup(int x)
{
    if(lx[ls[x]]) lx[x]=lx[ls[x]];
    else lx[x]=lx[rs[x]];
    if(rx[rs[x]]) rx[x]=rx[rs[x]];
    else rx[x]=rx[ls[x]];
    t[x]=t[ls[x]]^t[rs[x]];
    if(rx[ls[x]]&&lx[rs[x]]) t[x]^=(1ll*lx[rs[x]]*lx[rs[x]]-1ll*rx[ls[x]]*rx[ls[x]]);
    if(tg[ls[x]]&&tg[rs[x]]) tg[x]=1;
}
il void mdf(int &x,int l,int r,int ql,int qr)
{
//  cout<<l<<' '<<r<<endl;
    if(tg[x]) return;
    if(!x) x=++cnt;
    if(ql<=l&&r<=qr)
    {
        lx[x]=l;rx[x]=r;
        t[x]=calc(r-1)^calc(l-1);
        tg[x]=1;
        return;
    }
//  if(l!=r) cout<<l<<' '<<r<<endl; 
    int mid=(l+r)>>1;
    if(ql<=mid) mdf(ls[x],l,mid,ql,qr);
    if(qr>mid) mdf(rs[x],mid+1,r,ql,qr);
    //cout<<"qwq "<<ls[x]<<' '<<rs[x]<<endl;
    pushup(x);
}
signed main()
{
    int q=read();
    while(q--)
    {
        int opt=read();
        if(opt==1)
        {
            int l=read(),r=read();
        //  cout<<"lr:"<<l<<' '<<r;
            mdf(rt,1,1e9,l,r);
        }
        else printf("%lld\n",t[1]);
    }
}