这次是真的惨，码了将近2hours的可持久化线段树炸掉了！
而且本地拍了一万年也没发现哪里炸了。
T1 压位的入门题，话说这道题能拿个99分就可以了（100分要FFT）
对于暴力，就是暴力找所有不相同的i的个数，但是，我们发现对于这种01串的题目可以很舒服的压一下位
比如对于10011，十进制下就是19
而对于01110，十进制下是14
我们发现两个串的不同之处就是满足a[i]^b[i]=1的数对总数
因此我们可以对十进制数也进行xor，即19^14=31,31在二进制下为：11101，恰好满足以上的性质
所以我们可以直接用压位后的十进制数进行xor操作，最后统计这个数中有几个1即可
对于1的个数，可以做以下递推，对于每一个十进制数i，转化为二进制下1的个数为num[i],则
num[i]=num[i>>1]+（i&1）
然后就是压位+暴力找了
CODE
#include<cstdio>
using namespace std;
const int P=16,N=500005,M=1000005;
bool a[N],b[M];
int bl_a[N],bl_b[M],num[(1<<P)+5],n,m,q,p1,p2,len,ans,last;
char ch;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
int main()
{
register int i,j;
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
ch=tc(); while (ch=='-'||ch=='\n') ch=tc(); while (ch!=' '&&ch!='\n') a[n++]=ch-'0',ch=tc();
ch=tc(); while (ch=='-'||ch=='\n') ch=tc(); while (ch!=' '&&ch!='\n') b[m++]=ch-'0',ch=tc();
for (i=0;i<(1<<P);++i)
num[i]=num[i>>1]+(i&1);
for (i=0;i<n;++i)
for (j=0;j<P;++j)
{
if (i+j>=n) break;
bl_a[i]=(bl_a[i]<<1)|a[i+j];
}
for (i=0;i<m;++i)
for (j=0;j<P;++j)
{
if (i+j>=m) break;
bl_b[i]=(bl_b[i]<<1)|b[i+j];
}
read(q);
while (q--)
{
read(p1); read(p2); read(len);
p2=(p2^last)%(m-len+1);
i=ans=0;
while (i+P<len) ans+=num[bl_a[i+p1]^bl_b[i+p2]],i+=P;
while (i<len) ans+=a[i+p1]^b[i+p2],++i;
write(last=ans); putchar('\n');
}
return 0;
}
T2 考试的时候看了很久没看懂题意
其实理解了题意还是很可做的狗的
标算也比较难，这里放一个爆搜CODE吧
#include<cstdio>
using namespace std;
const int N=100005,mod=100000007;
bool f[N],t[N];
int n,m,a[N][3],ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc(); int flag=1;
while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
x*=flag;
}
inline bool get(int x)
{
if (x<0) return !f[-x]; else return f[x];
}
inline void check(void)
{
register int i;
for (i=1;i<=n;++i)
{
t[i]=get(a[i][1]);
if (a[i][0]>1) t[i]|=get(a[i][2]);
}
bool res;
for (res=t[1],i=2;i<=n;++i)
res^=t[i];
if (res) ans=ans==mod-1?0:ans+1;
}
inline void DFS(int now)
{
if (now>m) { check(); return; }
f[now]=1; DFS(now+1); f[now]=0; DFS(now+1);
}
int main()
{
register int i,j;
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
read(n); read(m);
for (i=1;i<=n;++i)
{
read(a[i][0]);
for (j=1;j<=a[i][0];++j)
read(a[i][j]);
}
DFS(1);
printf("%d",ans);
}
T3 这其实并不是一道大力数据结构题
离线操作,对于所有的操作4，从它的返回点向它连一条边，否则从i-1连一条边给它
然后就组成了一棵树，O(n）DFS即可，注意回溯的时候要反向操作
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int Q=300005,N=1005;
struct edge
{
int to,next;
}e[Q];
struct data
{
int opt,x,y;
bool vis;
}a[Q];
bool map[N][N],tag[N];
int head[Q],ans[Q],num[N],tot,n,m,q,k;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline void add(int x,int y)
{
e[++k].to=y; e[k].next=head[x]; head[x]=k;
}
inline void work(int now)
{
if (a[now].opt==1&&!(tag[a[now].x]^map[a[now].x][a[now].y])) map[a[now].x][a[now].y]^=1,++tot,++num[a[now].x],a[now].vis=1;
if (a[now].opt==2&&tag[a[now].x]^map[a[now].x][a[now].y]) map[a[now].x][a[now].y]^=1,--tot,--num[a[now].x],a[now].vis=1;
if (a[now].opt==3) tag[a[now].x]^=1,tot+=m-num[a[now].x]*2,num[a[now].x]=m-num[a[now].x];
}
inline void replay(int now)
{
if (a[now].opt==1&&a[now].vis) map[a[now].x][a[now].y]^=1,--tot,--num[a[now].x];
if (a[now].opt==2&&a[now].vis) map[a[now].x][a[now].y]^=1,++tot,++num[a[now].x];
if (a[now].opt==3) tag[a[now].x]^=1,tot+=m-num[a[now].x]*2,num[a[now].x]=m-num[a[now].x];
}
inline void DFS(int now)
{
work(now);
ans[now]=tot;
for (register int i=head[now];i!=-1;i=e[i].next)
DFS(e[i].to);
replay(now);
}
int main()
{
register int i;
memset(e,-1,sizeof(e));
memset(head,-1,sizeof(head));
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
read(n); read(m); read(q);
for (i=1;i<=q;++i)
{
read(a[i].opt); read(a[i].x);
if (a[i].opt<=2) read(a[i].y);
if (a[i].opt!=4) add(i-1,i); else add(a[i].x,i);
}
DFS(0);
for (i=1;i<=q;++i)
write(ans[i]),putchar('\n');
return 0;
}