T1 树上的数

有手就能在衡中$OJ$上过，但是$WaitingCoders$不行，就是这样

必须使用$O(n)$算法加上大力卡常，思路就是找子树内没更新的更新，更新过了直接$return$

1 #include
2 using namespace std;
3 int n,m,q1,vis[5000001],fa[5000001],a,b,X,Y,tmp,ans;
4 struct SNOW{int to,next;}e[5000001];int head[5000001],rp;
5 auto add=[](int x,int y){e[++rp]=(SNOW){y,head[x]};head[x]=rp;};
6 inline int read(){
7 int x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
10 return x*f;
11 }
12 inline void dfs(int x){
13 if(!vis[x])return;tmp+=vis[x];vis[x]=0;
14 for(int i=head[x];i;i=e[i].next) dfs(e[i].to);
15 }
16 namespace WSN{
17 inline short main(){
18 freopen("tree.in","r",stdin);
19 freopen("tree.out","w",stdout);
20 n=read();m=read();a=read();b=read();q1=read();X=read();Y=read();
21 fa[1]=0;fa[2]=1;add(1,2);vis[1]=vis[2]=1;
22 for(int i=3;i<=n;++i){
23 fa[i]=((1ll*fa[i-1]*a+b)^19760817)%(i-1)+1;
24 add(fa[i],i);vis[i]=1;
25 }
26 dfs(q1);
27 ans=n-tmp;
28 for(int i=2;i<=m;++i){
29 q1=(((1ll*q1*X+Y)^19760817)^(i<<1))%(n-1)+2;
30 dfs(q1);
31 ans^=n-tmp;
32 }
33 printf("%d\n",ans);
34 return 0;
35 }
36 }
37 signed main(){return WSN::main();}

T2 时代的眼泪

名字一看挺猛，（不过原来的那次队长快跑+影魔+抛硬币让我知道这都是吓唬人的）

显然的换根$dp$，但是考场上没搞清楚贡献增减在哪里，于是本身写了一个线段树维护$set$准备优化换根

没有用上，就用这个打暴力，造成了比较奇迹的$O(qnlog^3n)$，也是没谁了

更sb的是没用$multiset$导致爆蛋蛋！！！！（大样例很水，$w_i$互不相同，就没发现不对劲）

于是这次考试垫底了。。。。

1 #include
2 #define fo(i,x,y) for(int i=(x);i<=(y);++i) 3 #define fr(i,x,y) for(int i=(x);i>=(y);--i)
4 #define int long long
5 using namespace std;
6 inline int read(){
7 int x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 10 return x*f; 11 } 12 inline void swap_(int &a,int &b){a^=b^=a^=b;} 13 const int NN=1e6+10,inf=1e9; 14 int n,q,w[NN]; 15 struct SNOW{int to,next;}e[NN<<1];int head[NN],rp; 16 inline void add(int x,int y){ 17 e[++rp]=(SNOW){y,head[x]};head[x]=rp; 18 e[++rp]=(SNOW){x,head[y]};head[y]=rp; 19 } 20 int dfn[NN],rk[NN],top[NN],siz[NN],fa[NN],dep[NN],son[NN],cnt; 21 struct SNOWtree{ 22 #define lid (id<<1) 23 #define rid (id<<1|1) 24 #define sit multiset::iterator
25 int ll[NN<<2],rr[NN<<2]; 26 struct node{ 27 int w; mutable int id; 28 bool operator<(const node&a)const{return w s[NN<<2]; 30 inline void build(int id,int l,int r){ 31 ll[id]=l;rr[id]=r; int tmp=0; 32 for(int i=l;i<=r;++i) s[id].insert(node{w[rk[i]],0}); 33 for(auto &it:s[id]) it.id=(++tmp); 34 if(l==r) return; int mid=(l+r)>>1;
35 build(lid,l,mid);build(rid,mid+1,r);
36 }
37 inline int query(int id,int l,int r,int v){
38 if(l<=ll[id]&&rr[id]<=r){ 39 sit pos=s[id].upper_bound(node{v,0}); 40 if(pos==s[id].end()) return 0; 41 sit ed=s[id].end(); --ed; 42 return ed->id-pos->id+1;
43 }int mid=ll[id]+rr[id]>>1,ans=0;
44 if(l<=mid) ans+=query(lid,l,r,v); 45 if(r>mid) ans+=query(rid,l,r,v);
46 return ans;
47 }
48 }tr;
49 namespace tree_division{
50 inline void dfs1(int f,int x){
51 fa[x]=f; dep[x]=dep[f]+1; siz[x]=1;
52 for(int i=head[x];i;i=e[i].next){
53 int y=e[i].to; if(y==f) continue;
54 dfs1(x,y); siz[x]+=siz[y];
55 if(siz[son[x]]dfn[y]) swap_(x,y);
73 ans+=tr.query(1,dfn[x],dfn[y],v);
74 return ans;
75 }
76 }using namespace tree_division;
77 int dis[NN],num,an;
78 inline void discrete(){
79 sort(dis+1,dis+n+1); num=unique(dis+1,dis+n+1)-dis-1;
80 for(int i=1;i<=n;++i)w[i]=lower_bound(dis+1,dis+num+1,w[i])-dis;
81 }
82 namespace WSN{
83 inline short main(){
84 // freopen("in.in","r",stdin);//freopen("bl.out","w",stdout);
85 freopen("tears.in","r",stdin);
86 freopen("tears.out","w",stdout);
87 n=read(); q=read();
88 for(int i=1;i<=n;++i) w[i]=read(),dis[i]=w[i];
89 discrete();
90 // for(int i=1;i<=n;i++) cout<<w[i]<<" ";cout<<endl;
91 for(int i=1,u,v;i<n;++i){
92 u=read(); v=read(); add(u,v);
93 } dfs1(0,1); dfs2(1,1); tr.build(1,1,n);
94 int root;
95 while(q--){
96 root=read();an=0;
97 for(int i=1;i<=n;++i)
98 an+=query(root,i,w[i]);
99 printf("%lld\n",an);
100 }
101 return 0;
102 }
103 }
104 signed main(){return WSN::main();}

TLE 25

这代码在一般$OJ$上应该是可以拿到$40$的，但是并不知道$WaitinCoders$换了界面没换测评姬。。。

于是这道题就成了卡常神题，不能用线段树，用树状数组

1 #include
2 #define si(i,x) for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)
3 typedef long long LL;
4 using namespace std;
5 namespace AE86{
6 auto read=[](){
7 LL x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 10 return x*f; 11 }; 12 auto write=[](int x,char opt='\n'){ 13 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-'); 14 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 15 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);
16 };auto swap_=[](int&a,int&b){a^=b^=a^=b;};
17 }using namespace AE86;
18 const int NN=1e6+10;
19 int n,q,w[NN],root,dis[NN],num;
20 struct SNOW{int to,next;}e[NN<<1];int head[NN],rp;
21 auto add=[](int x,int y){e[++rp]=(SNOW){y,head[x]};head[x]=rp;};
22 namespace BIT{
23 int c[NN];
24 auto update=[](int x,int v){++x;while(x<NN)c[x]+=v,x+=(x&(-x));};
25 auto query=[](int x){int ans=0;++x;while(x)ans+=c[x],x-=(x&(-x));return ans;};
26 }using namespace BIT;
27 auto discrete=[](){
28 sort(dis+1,dis+n+1);num=unique(dis+1,dis+n+1)-dis-1;
29 for(int i=1;i<=n;++i)w[i]=lower_bound(dis+1,dis+num+1,w[i])-dis;
30 };
31 LL dp[NN];int g[NN],d[NN];
32 inline void dfs(int f,int x){
33 dp[1]+=query(num)-query(w[x]);update(w[x],1);
34 si(i,x) if(y!=f) dfs(x,y); update(w[x],-1);
35 }
36 inline void prework(int f,int x){
37 d[x]-=query(w[x]-1);
38 if(f) g[x]-=query(w[f]-1);
39 update(w[x],1);
40 si(i,x) if(y!=f) prework(x,y);
41 if(f) g[x]+=query(w[f]-1);
42 d[x]+=query(w[x]-1);
43 }
44 inline void reroot(int f,int x){si(i,x) if(y!=f) dp[y]=dp[x]-g[y]-d[y]+query(w[y]-1),reroot(x,y);}
45 namespace WSN{
46 inline short main(){
47 // freopen("in.in","r",stdin);//freopen("bl.out","w",stdout);
48 freopen("tears.in","r",stdin);freopen("tears.out","w",stdout);
49 n=read();q=read();for(int i=1;i<=n;++i)dis[i]=w[i]=read();
50 for(int i=1,u,v;i<n;++i)u=read(),v=read(),add(u,v),add(v,u);
51 discrete();dfs(0,1);prework(0,1);reroot(0,1);
52 while(q--)root=read(),printf("%lld\n",dp[root]);
53 return 0;
54 }
55 }
56 signed main(){return WSN::main();}

T3 传统艺能

话不多说先$moBai$！！矩阵乘法带师！！

基础的有一个$dp$，$f_{ch}=\sum\limits_{i='A'}^{'C'}f_i+1$

这个东西整成向量矩阵后直接一手矩阵加速递推，$A,B,C$三种不同的转移矩阵

直接在线段树上维护他们的区间乘积即可

1 #include
2 #define int long long
3 using namespace std;
4 auto read=[](){
5 int x=0,f=1;char ch=getchar();
6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 8 return x*f; 9 }; 10 const int mod=998244353,NN=1e5+5; 11 int n,m; 12 char s[NN],ch[3]; 13 namespace matrix{ 14 struct Ma{ 15 int m[4][4]; 16 Ma(){memset(m,0,sizeof(m));} 17 inline void pre(){m[0][0]=m[1][1]=m[2][2]=m[3][3]=1;} 18 Ma operator*(const Ma&a)const{Ma c; 19 for(int i=0;i<4;++i)for(int j=0;j<4;++j){ 20 for(int k=0;k<4;++k)c.m[i][j]+=m[i][k]*a.m[k][j]; 21 c.m[i][j]%=mod; 22 } 23 return c; 24 } 25 }A,B,C; 26 struct Li{ 27 int l[4]; 28 Li(){memset(l,0,sizeof(l));} 29 Li operator*(const Ma&a)const{Li c; 30 for(int i=0;i<4;++i)for(int j=0;j<4;++j) 31 (c.l[i]+=l[j]*a.m[i][j])%=mod; 32 return c; 33 } 34 }F; 35 auto prework=[](){ 36 A.m[0][0]=A.m[0][1]=A.m[0][2]=A.m[0][3]=A.m[1][1]=A.m[2][2]=A.m[3][3]=1; 37 B.m[0][0]=B.m[1][0]=B.m[1][1]=B.m[1][2]=B.m[1][3]=B.m[2][2]=B.m[3][3]=1; 38 C.m[0][0]=C.m[1][1]=C.m[2][0]=C.m[2][1]=C.m[2][2]=C.m[2][3]=C.m[3][3]=1; 39 F.l[3]=1; 40 }; 41 inline Ma get(char s){if(s=='A') return A;else if(s=='B') return B;else return C;}; 42 }using namespace matrix; 43 struct SNOWtree{ 44 #define lid (id<<1) 45 #define rid (id<<1|1) 46 int ll[NN<<2],rr[NN<<2]; Ma sm[NN<<2]; 47 inline void pushup(int id){if(ll[id]==rr[id])return;sm[id]=sm[lid]*sm[rid];} 48 inline void build(int id,int l,int r){ 49 ll[id]=l;rr[id]=r;if(l==r)return sm[id]=get(s[l]),void(); 50 int mid=l+r>>1;build(lid,l,mid);build(rid,mid+1,r);pushup(id);
51 }
52 inline void update(int id,int pos,Ma g){
53 if(ll[id]==rr[id]) return sm[id]=g,void();int mid=ll[id]+rr[id]>>1;
54 if(pos<=mid)update(lid,pos,g);else update(rid,pos,g);pushup(id); 55 } 56 inline Ma query(int id,int l,int r){ 57 if(l<=ll[id]&&rr[id]<=r)return sm[id];int mid=ll[id]+rr[id]>>1;Ma ans;ans.pre();
58 if(l<=mid)ans=ans*query(lid,l,r);if(r>mid)ans=ans*query(rid,l,r);return ans;
59 }
60 }tr;
61 namespace WSN{
62 inline short main(){
63 freopen("string.in","r",stdin);freopen("string.out","w",stdout);
64 n=read();m=read();scanf("%s",s+1);prework();tr.build(1,1,n);
65 while(m--){
66 int opt=read();
67 if(opt==1){int p=read();scanf("%s",ch);Ma g=get(ch[0]);tr.update(1,p,g);}
68 else{
69 int l=read(),r=read();Li g;g=F*tr.query(1,l,r);
70 printf("%lld\n",(g.l[0]+g.l[1]+g.l[2])%mod);
71 }
72 }
73 return 0;
74 }
75 }
76 signed main(){return WSN::main();}