今天又是考的非常糟糕的一天
t1看错题了，想了半个小时没想出来55分，气而转t2,想完60分以后，想正解，我**了，竟然没想起来s={a,z}|{A,Z},还以为s里随便取的，然后是t3，看了一眼好像见过，但是好像没写，推了一会dp感觉不能做，就看t4去了，t4想了很长时间，一直以为是组合数+构造什么的，质因子数==2想了一会头疼就算了，一看表就9点多了，回去看t1,打了暴力过不了样例，仔细一看题，发现一直都看错题了，hehe，赶紧写完55分一看9.44，想了一会以为是什么神仙数据结构，就走额，很快把第二题暴力打完就走了，t3暴力都不会，赶紧走额，打了t4的暴力，还行，打完就11.20了，无意间发现质因子数==2的情况可以打表，但是来不及了，于是赶紧打了10的几次方的表，就交了
反思：
看题看错，太**了。
没有思路，就再看一眼题面，看着像打表的就先写，注意数据里的标出来的特殊信息
题解：
t1:
发现 a[i] 对于答案的贡献就是它被包含的次数，经过手推，发现只有当区间长度为奇数，并且是区间的第一个数，第三个数，第r-l+1个数时才有贡献，套一个树状数组就行了
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N],n; int c[N][2]; void add(int x,int v) { int k=x&1; while(x<=n) { c[x][k]^=v; x+=x&-x; } } int query(int x) { if(x<0) return 0; int res=0; int k=x&1; while(x) { res^=c[x][k]; x-=x&-x; } return res; } int main() { // freopen("xor.in","r",stdin); // freopen("xor.out","w",stdout); int m; cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) add(i,a[i]); int l,r,ok; while(m--) { scanf("%d %d %d",&ok,&l,&r); if(ok==1) add(l,a[l]^r),a[l]=r; else { if((r-l+1)%2==0) { printf("0\n"); continue; } printf("%d\n",query(r)^query(l-2));//保持 奇偶性 } } return 0; }
t2:
hehe,map记一下差分数组就行了
t3:
奇怪的dp
f[c][x][y][z] 当前点是颜色c，已经用了x个颜色0，y个颜色1，z个颜色2
不同颜色转移一下就好了，注意两个状态之间转移的贡献不是直接走过去
t4:
奇怪的爆搜
明天再说吧