智力彻底没有了。。。看来再也拿不到奖金了QAQ。。。

因为数据是9B1L，所以我们可以hash试一下数据。。。

#include
     
      #include
      
       #include
       
        #include
        
         #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)using namespace std;inline int read() {    int x=0,f=1;char c=getchar();    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) x=x*10+c-'0';    return x*f;}typedef unsigned long long ll;int main() {	int n=read();ll ans=0,ans2=0;	rep(i,1,n) {		ll c;scanf("%llu",&c);		ans^=c;ans2^=(c%52501);	}	if((ans&1)&&(!(ans&2))&&(ans&4)&&(ans2&1)&&(!(ans2&2))) puts("L");	else puts("B");	return 0;}
        
       
      
     

这道数位DP题应该还是不错的，我们先考虑给定一个数消成0的最小步数如何计算。

从高位到低位依次考虑每一位，设当前数字为x，将栈里所有大于x的数字删除，如果此时栈里没有数字x则加入，并且答案+1。

我们把这个想法套到数位DP中，设f[len][S][k][c]表示前len位，栈中集合为S，当前已经进行过k次操作，当前的数与给定数的大小关系。

转移时枚举下一位填什么数字即可。

#include
     
      #include
      
       #include
       
        #include
        
         #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)using namespace std;inline int read() {    int x=0,f=1;char c=getchar();    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) x=x*10+c-'0';    return x*f;}typedef long long ll;int k,bit[20];ll f[20][1050][20][2];//f[len][S][sumv][
         >j&1) S2^=(1<
         
          >y&1) k2--;			f[i][S2][k2][c|(y
         
        
       
      
     

枚举（i,j）= k，考虑维护S[k]=sigma{A[i]  |  k|i}，然后再容斥一下就能计算出每次询问的答案了。

所以我们预处理出来所有数的因数和mu函数，然后就能每次O(sqrt(N))实现了。

#include
     
      #include
      
       #include
       
        #include
        
         #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)using namespace std;inline int read() {    int x=0,f=1;char c=getchar();    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) x=x*10+c-'0';    return x*f;}const int maxn=100010;const int maxm=2000010;typedef long long ll;int first[maxn],next[maxm],to[maxm],cnt,e;void Addpri(int u,int v) {to[++e]=v;next[e]=first[u];first[u]=e;}int vis[maxn],mu[maxn],pri[maxn];void init(int n) {	rep(i,1,n) for(int j=i;j<=n;j+=i) Addpri(j,i);	mu[1]=1;	rep(i,2,n) {		if(!vis[i]) pri[++cnt]=i,mu[i]=-1;		rep(j,1,cnt) {			if(pri[j]*i>n) break;			vis[pri[j]*i]=1;			if(i%pri[j]==0) {mu[i*pri[j]]=0;continue;}			mu[i*pri[j]]=-mu[i];		}	}}int B[maxn],sum;int n,m,A[maxn];void Add(int x,int v) {	sum+=v;	for(int i=first[x];i;i=next[i]) B[to[i]]+=v*mu[to[i]];}int query(int x) {	int res=0;	for(int i=first[x];i;i=next[i]) res+=B[to[i]];	return res;}int main() {	n=read();m=read();init(n);	rep(i,1,n) Add(i,A[i]=read());	rep(i,1,m) {		int t=read(),x=read();		if(t==2) printf("%d\n",query(x));		else {			int v=read();Add(x,v-A[x]);			A[x]=v;		}	}	return 0;}
        
       
      
     

我的做法是基于AC自动机的。

考虑先将证言串和言弹串放在一棵AC自动机上，则一个言弹对一个证言的伤害即为证言有多少前缀在言弹对应fail树的子树。

考虑对每个询问以证言出现时间为第一关键字、以询问时间为第二关键字、AC自动机上位置为第三关键字，然后直接跑树上莫队即可。

时间复杂度为O(N^(5/3)logN)。但因为常数较小所以还可以跑过。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)using namespace std;inline int read() {    int x=0,f=1;char c=getchar();    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) x=x*10+c-'0';    return x*f;}typedef long long ll;const int maxn=200010;int SIZE,ch[maxn][26],pa[maxn],cnt;int insert(int p,int c) {	if(!ch[p][c]) ch[p][c]=++cnt;	pa[ch[p][c]]=p;	return ch[p][c];}int f[maxn],que[maxn],first1[maxn],first2[maxn],e1,e2;struct Edge {	int to,next;}edges1[maxn],edges2[maxn];void AddEdge1(int u,int v) {edges1[++e1]=(Edge){v,first1[u]};first1[u]=e1;}void AddEdge2(int u,int v) {edges2[++e2]=(Edge){v,first2[u]};first2[u]=e2;}int dep[maxn],sta[maxn],cur[maxn],blo[maxn],top,tmp;void dfs1(int x) {	dep[x]=dep[pa[x]]+1;cur[x]=top;	for(int i=first1[x];i;i=edges1[i].next) {		int v=edges1[i].to;dfs1(v);		if(top-cur[x]>SIZE) {			tmp++;			while(top>cur[x]) blo[sta[top--]]=tmp;		}	}	sta[++top]=x;}int st[maxn],en[maxn];void dfs2(int x) {	st[x]=++tmp;	for(int i=first2[x];i;i=edges2[i].next) dfs2(edges2[i].to);	en[x]=tmp;}void getfail() {	int l=1,r=0;	rep(c,0,25) if(ch[0][c]) que[++r]=ch[0][c];	while(l<=r) {		int x=que[l++],v;		rep(c,0,25) if(v=ch[x][c]) {			que[++r]=v;int j=f[x];			while(j&&!ch[j][c]) j=f[j];			f[v]=ch[j][c];		}	}	rep(i,1,cnt) AddEdge1(pa[i],i);	dfs1(0);while(top) blo[sta[top--]]=tmp;	rep(i,1,cnt) AddEdge2(f[i],i);	tmp=0;dfs2(0);}int posa[maxn],tima[maxn],posb[maxn],ca,cb;int n,m,q,t[maxn],p[maxn],blt[maxn];struct Query {	int b,t,x;	bool operator < (const Query& ths) const {		if(blo[x]!=blo[ths.x]) return blo[x]
          
           Q[i].b) U(p[--l],1); while(r
           
            
             Q[i].t) U(p[r--],-1); Move(cx,Q[i].x);cx=Q[i].x; ans[Q[i].t]=curans; } rep(i,1,n) if(ans[i]>=0) printf("%lld\n",ans[i]); return 0;}