A. Nutella’s Life

斜率优化DP显然，CDQ分治后按$a$排序建线段树，每层维护凸包，查询时不断将队首弹出即可。

时间复杂度$O(n\log^2n)$。

#include
     
      #include
      
       using namespace std;typedef long long ll;typedef pair
       
        P;const int N=100010,M=262150;int n,i,a[N],cb;ll f[N],g[N],w[N],ans;int st[M],en[M],tot,q[4000000];int H;P b[N];inline void up(ll&a,ll b){a
        
         pos(q[tot],x))tot--;	q[++tot]=x;}void build(int x,int l,int r){	if(l==r){		st[x]=en[x]=++tot;		q[tot]=b[l].second;		return;	}	int mid=(l+r)>>1;	build(x<<1,l,mid);	build(x<<1|1,mid+1,r);	int i=st[x<<1],j=st[x<<1|1];	H=st[x]=tot+1;	while(i<=en[x<<1]&&j<=en[x<<1|1]){		if(q[i]
         
          >1;	ask(x<<1,a,mid,d,p);	if(d>mid)ask(x<<1|1,mid+1,b,d,p);}void solve(int l,int r){	if(l==r){		g[l]=f[l]-l-1LL*l*l;		up(ans,f[l]-1LL*(n-l)*(n-l+1));		return;	}	int mid=(l+r)>>1,i;	solve(l,mid);	cb=0;	for(i=l;i<=mid;i++)b[++cb]=P(a[i],i);	sort(b+1,b+cb+1);	tot=0;	build(1,1,cb);	for(i=mid+1;i<=r;i++){		if(a[i]
         
        
       
      
     

　　

B. Oleg and Data Science

若$R<Q$，那么显然$\bmod Q$操作无效，故答案为无穷。

否则若$\lfloor\frac{L}{Q}\rfloor=\lfloor\frac{R}{Q}\rfloor$，则答案为$Q\lfloor\frac{L}{Q}\rfloor$的因子个数。

否则答案为$Q$的因子个数。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

C. Christmas Garland

首先将相邻同色块合并，建立一张图，每个点表示一种颜色的灯，两点间的边表示这两种颜色相邻的有多少个，那么答案为亮着的灯数减去同时亮着的边数。

将点按照度数大小以$\sqrt{m}$为界分成小点和大点，对于每个点维护$w_x$表示周围有多少个小点亮着。

那么若操作小点，则枚举它所有相连的边，修改其$w$，同时对于相邻的大点计算对答案的贡献。

若操作大点，则枚举它所有与大点相连的边，计算贡献。

时间复杂度$O(n\sqrt{n})$。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef pair
         
          P;const int N=200010;int n,ce,_,m,Q,i,j,x,y,have[N],tot,ans,lim;int d[N],a[N],f[N],w[N];vector
          
g[N],gg[N];vector
          
::iterator it;struct E{int x,y;}e[N];inline bool cmp(const E&a,const E&b){return a.x==b.x?a.y
           
            
             =lim&&d[y]>=lim)gg[x].push_back(P(y,z));}int main(){ scanf("%d%d%d",&_,&m,&Q); while(_--){ scanf("%d",&x); if(x!=a[n])a[++n]=x; } for(i=1;i<=n;i++)have[a[i]]++; for(i=1;i
             
              y)swap(x,y); e[++ce].x=x; e[ce].y=y; } sort(e+1,e+ce+1,cmp); for(i=1;i<=ce;i=j){ for(j=i;j<=ce&&e[i].x==e[j].x&&e[i].y==e[j].y;j++); add(e[i].x,e[i].y,j-i); add(e[i].y,e[i].x,j-i); } lim=sqrt(lim); for(i=1;i<=ce;i=j){ for(j=i;j<=ce&&e[i].x==e[j].x&&e[i].y==e[j].y;j++); addd(e[i].x,e[i].y,j-i); addd(e[i].y,e[i].x,j-i); } while(Q--){ scanf("%d",&x); if(d[x]
              
               first]+=it->second; if(d[it->first]>=lim&&f[it->first])ans+=it->second; } }else{ tot-=have[x]; ans-=w[x]; for(it=g[x].begin();it!=g[x].end();it++){ w[it->first]-=it->second; if(d[it->first]>=lim&&f[it->first])ans-=it->second; } } }else{ if(f[x]==0){ tot+=have[x]; ans+=w[x]; for(it=gg[x].begin();it!=gg[x].end();it++)if(f[it->first])ans+=it->second; }else{ tot-=have[x]; ans-=w[x]; for(it=gg[x].begin();it!=gg[x].end();it++)if(f[it->first])ans-=it->second; } } f[x]^=1; printf("%d\n",tot-ans); }}
              
             
            
           
         
        
       
      
     

　　

D. Anna and Lucky Tickets

问题即统计有多少长度为$n$的回文十进制数字串满足奇数位数位和等于偶数位数位和。

若$n$是偶数，那么因为回文的性质，左半部分在右半部分奇偶性反转，故奇数位和必定等于偶数位和，故$ans=10^{\frac{n}{2}}$。

若$n$是奇数，那么奇数位要填$[0,9]$，偶数位要填$[-9,0]$，将所有偶数位都加上$9$，再枚举中间的数，则问题转化为统计$\sum_{i=1}^n x_i=m,0\leq x_i\leq 9$的解数。

考虑容斥，枚举有$k$个$x_i$必定突破了上限，剩下的不管，将上限从$m$中减掉后用隔板法计算，则$ans=\sum_{k=0}^n (-1)^kC(n,k)C(m-10k+n-1,n-1)$。

时间复杂度$O(n)$。

#include
     
      const int N=10000010,P=1000000007;int n,i,ans,even,odd,all,fac[N],inv[N];inline int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}inline int C(int n,int m){  if(n
     

　　

E. Octopus

分类大讨论。

 

F. Secret Permutation

首先进行一轮迭代$Q(zero,i,zero)$即可找到$0$的位置。

将剩下$n-1$个数放入集合$S$，每次从$S$中随机选择两个$x,y$，询问$Q(x,y,zero)$，即可有很大概率排除掉$x$和$y$，期望$\frac{n}{2}$次可以得到$1$的位置。

那么知道$1$之后，不断询问$Q(i,one,one)$即可得到所有数的位置。

询问次数期望为$2.5n\leq 12512$。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=5010;int n,i,A,B,x,m,q[N],f[N],one,zero;inline int ask(int a,int b,int c){  printf("? %d %d %d\n",a,b,c);  fflush(stdout);  int t;  scanf("%d",&t);  return t;}int main(){  srand(time(NULL));  scanf("%d",&n);  if(n==1){    puts("! 0");    fflush(stdout);    return 0;  }  for(i=0;i
         
          1){    A=q[x=rand()%m];    swap(q[x],q[--m]);    B=q[x=rand()%m];    swap(q[x],q[--m]);    x=ask(A,B,zero);    if(x==A)q[m++]=B;    if(x==B)q[m++]=A;  }  f[A=one=q[0]]=1;  for(i=2;i
         
        
       
      
     

　　

G. Polygon Rotation

留坑。

 

H. Mikhail’s Problem

论文题。回文树求出每个回文等差数列消失的位置，树状数组维护，时间复杂度$O(n\log n)$。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=100010;int sz,last,go[N][26],len[N],diff[N],link[N],series_link[N],baby[N];int n,m,i,j,k,x,y,f[N],bit[N];int ans[N];vector
         
          
            >poses[N],que[N];char s[N];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline int go_until_pal(int i,int v){ while(s[i]!=s[i-len[v]-1])v=link[v]; return v;}inline pair
           
            
             ,vector
             
               >add_char(int i){ last=go_until_pal(i,last); int&v=go[last][s[i]-'a']; if(v==-1){ v=sz++; len[v]=len[last]+2; if(!last)link[v]=1; else{ last=go_until_pal(i,link[last]); link[v]=go[last][s[i]-'a']; } diff[v]=len[v]-len[link[v]]; if(diff[v]==diff[link[v]]){ baby[v]=baby[link[v]]; series_link[v]=series_link[link[v]]; }else{ baby[v]=v; series_link[v]=link[v]; } } last=v; pair
              
               
                ,vector
                
                  >ans; for(int u=v;u!=1;u=series_link[u]){ int B=baby[u]; vector
                 
                  
                    >&vec=poses[B]; int left=i-len[u]+1; if(vec.size()&&vec.back().first==left)vec.back().second=len[u]; else vec.push_back(make_pair(left,len[u])); ans.first.push_back(i-len[B]+1); if(vec.size()!=1){ int L=vec[vec.size()-2].first, len_=vec[vec.size()-2].second, R=L+len_-1, L_=R-len[u]+1; ans.second.push_back(L_); } if(vec.size()!=1)if(vec[vec.size()-1].second==vec[vec.size()-2].second){ vec[vec.size()-2]=vec[vec.size()-1]; vec.pop_back(); } } return ans;}inline void add(int x,int p){for(f[x]+=p;x<=n;x+=x&-x)bit[x]+=p;}inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}int main(){ scanf("%s%d",s+1,&m); n=strlen(s+1); sz=2,last=0,len[0]=-1; for(i=0;i<=n+5;i++)memset(go[i],-1,sizeof(go[i])); for(i=0;i
                   

,vector

>vec=add_char(i); vector

adding=vec.first,deleting=vec.second; for(j=0;j