T1 异或

给你\(n\)个形如\([l_i,r_i]\)区间，设\(S_i=\bigcup_{j=1}^{i}[l_j,r_j]\)，对于所有\(i\in[1,n]\)，求\(\sum_{x,y\in S_i,x\leq y}[x\) \(xor\) \(y\)在二进制下一的个数有奇数个\(]\)。
\(n\leq10^5,0\leq l\leq r\leq2^{31}-1\)

sol：

首先发现维护的内容是区间并，想到有一个绝配的数据结构叫线段树。因为\(l\)和\(r\)的范围可以到\(2^{31}-1\)，所以考虑动态开点或离散化。然后因为两个数异或后\(1\)的个数的奇偶性，与原来两个数\(1\)的个数之和的奇偶性相同，令\(X\)为区间内有几个含奇数个\(1\)的数，\(Y\)为有几个含偶数个\(1\)的数，所以只要分别处理出\(X\)和\(Y\)，\(X\times Y\)即是答案。
方法1：动态开点线段树。这时会有一个非常良好的性质，就是对于一个线段树上的区间\([l,r]\)，\(X\)的个数与\(Y\)的个数相等，于是一个区间的贡献可以在\(O(1)\)的时间内计算。
方法2：离散化+线段树。离散后可以不用动态开点，节省了空间，但同时失去了上一种做法的性质。现在继续考虑如何计算\(X\)和\(Y\)。我们把\(X_{[l,r]}\)拆成\(X_{[0,r]}-X_{[0,l-1]}\)，对于\(Y\)同理。对于区间\([0,a]\)，若\(a\)是奇数，则\(X_{[0,a]}=\frac{a}{2}+1\)，若\(a\)为偶数，则还要判断\(a\)是否对\(X\)造成贡献。
方法3：离散化+set。常数有点大。Orz xuyuan
方法1代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
const int N=100005,maxn=(1<<31)-1;
int n,cnt=1;
struct node{int l,r,data1,data2;bool vis;} st[N<<5];
void inst(int x,int l,int r,int lb,int rb){
    if(lb==rb){
        int num=0;
        for(int i=lb;i>0;i>>=1)
            if(i&1) num++;
        if(num&1) st[x].data1=1;
        else st[x].data1=0;
        st[x].data2=1-st[x].data1;
        st[x].vis=1;return;
    }
    if(l<=lb&&r>=rb){
        st[x].data2=st[x].data1=(rb-lb+1)>>1;
        st[x].vis=1;return;
    }
    int mid=(1ll*lb+rb)>>1;
    if(st[x].l==0) st[x].l=++cnt;
    if(l<=mid&&!st[st[x].l].vis) inst(st[x].l,l,r,lb,mid);
    if(st[x].r==0) st[x].r=++cnt;
    if(r>mid&&!st[st[x].r].vis) inst(st[x].r,l,r,mid+1,rb);
    st[x].data1=st[st[x].l].data1+st[st[x].r].data1;
    st[x].data2=st[st[x].l].data2+st[st[x].r].data2;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
        inst(1,x,y,0,maxn);
        printf("%lld\n",1ll*st[1].data1*st[1].data2);
    }
    return 0;
}

T2 图论

给一个\(n\)个点的无向连通图，求解任意一种添加边的方式，使图变成一个连通的欧拉回路。
\(2\leq n\leq2000\)

sol：

思路1：首先对于那些奇数度的点，要想办法把它们变成偶数度。考虑建一张反图，在图上增广，具体就是对于两个奇数度的点，在反图上找到任一条路径，反转边的存在情况（原来选的边不选，原来不选的边选）。结束后整个图的点都为偶数度了，但不保证连通。当连通块个数大于两个时，只要把它们串成一个环即可；当连通块个数等于两个时，可以考虑在某一块中删除一条已有，或增加一条没有，且可选可不选的边，再把那条边的两个端点连向另一块中的某个点。
思路2：对于一个奇数个点的图，完全图显然是一个解；对于一个偶数个点的图，考虑在完全图中删除\(n/2\)条边，做法与上一种类似。
思路1代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
const int N=1005;
int n,deg[N],st[N],ve[N],rev[N][N],ch[N][N],cnt,num;
char p[N][N];
bool vis[N],im;
void dfs(int x,int y,int la){
    vis[x]=1;
    for(int i=1;i<=n;i++){
        if(!rev[x][i]||i==la) continue;
        if(i==y){ch[x][i]^=1;ch[i][x]^=1;im=1;return;}
        if(vis[i]) continue;
        ch[x][i]^=1;ch[i][x]^=1;
        dfs(i,y,x);
        if(im) return;
        ch[x][i]^=1;ch[i][x]^=1;
    }
}
void print(){
    puts("Yes");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            if(p[i][j]=='1'||ch[i][j]||ch[j][i]) putchar('1');
            else putchar('0');
        puts("");
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",p[i]+1);
        for(int j=1;j<=n;j++){
            if(p[i][j]=='1') deg[j]++;
            if(p[i][j]=='1'||i==j) rev[i][j]=0;
            else rev[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(deg[i]&1) st[++cnt]=i;
    }
    if(cnt&1){puts("No");return 0;}
    for(int i=1;i<=cnt;i+=2){
        memset(vis,0,sizeof(vis));
        im=0;dfs(st[i],st[i+1],0);
        if(!im){puts("No");return 0;}
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(ch[i][j]) deg[j]++;
        }
    for(int i=1;i<=n;i++)
        if(deg[i]==0) ve[++num]=i;
    if(num==1){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(ch[i][j]){
                    ch[i][j]=ch[j][i]=0;
                    ch[ve[1]][i]=ch[i][ve[1]]=1;
                    ch[ve[1]][j]=ch[j][ve[1]]=1;
                    print();return 0;
                }
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(ch[i][j]==0&&i!=j&&p[i][j]=='0'){
                    ch[i][j]=ch[j][i]=1;
                    ch[ve[1]][i]=ch[i][ve[1]]=1;
                    ch[ve[1]][j]=ch[j][ve[1]]=1;
                    print();return 0;
                }
            }
        puts("No");return 0;
    }
    if(num==n){
        for(int i=1;i<n;i++)
            ch[i][i+1]=ch[i+1][i]=1;
        ch[n][1]=ch[1][n]=1;
        print();return 0;
    }
    int x,y;
    for(int i=1;i<=n;i++)
        if(deg[i]>0){
            x=i;
            for(int j=i+1;j<=n;j++)
                if(deg[j]>0){y=j;break;}
            break;
        }
    ch[x][ve[1]]=ch[ve[1]][x]=1;
    ch[y][ve[1]]=ch[ve[1]][y]=1;
    ch[x][ve[2]]=ch[ve[2]][x]=1;
    ch[y][ve[num]]=ch[ve[num]][y]=1;
    for(int i=2;i<num;i++){
        ch[ve[i]][ve[i+1]]=ch[ve[i+1]][ve[i]]=1;
    }
    print();return 0;
}

T3 乘积

以后补吧。