T1 yuuustu：
可以对两边取对数，然后就转化为两个double的比较，时间复杂度$O(n)$
然后我就用神奇0.4骗分水过
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e6+10;
4 struct BigInt{
5 int a[100005];
6 BigInt(){memset(a,0,sizeof(a));a[0]=a[1]=1;}
7 BigInt friend operator * (BigInt x,int y){
8 int len=x.a[0],las=0;
9 for(register int i=1;i<=len;++i){
10 x.a[i]=x.a[i]*y+las;
11 las=x.a[i]/10;
12 x.a[i]%=10;
13 if(i==len&&las) ++len;
14 }
15 return x.a[0]=len,x;
16 }
17 void print(){
18 for(int i=a[0];i>=1;--i) cout<<a[i];
19 }
20 };
21 inline bool chk(BigInt a,BigInt b){
22 for(int i=0;i<=a.a[0];++i) if(a.a[i]!=b.a[i]) return 0;
23 return 1;
24 }
25 inline bool cmp(BigInt a,BigInt b){//x^y y!
26 if(a.a[0]==b.a[0]) if(chk(a,b)) return 1;
27 if(a.a[0]^b.a[0]) return a.a[0]<b.a[0];
28 else{
29 for(register int i=a.a[0];i>=1;--i){
30 if(a.a[i]==b.a[i]) continue;
31 if(a.a[i]>b.a[i]) return 0;
32 else if(a.a[i]<b.a[i]) return 1;
33 }
34 }
35 }
36 void work_1(int x,int y){
37 if(x>y*0.4) puts("No");
38 else puts("Yes");
39 }
40 int main(){
41 freopen("yuuutsu.in","r",stdin);
42 freopen("yuuutsu.out","w",stdout);
43 int T;
44 scanf("%d",&T);register int x,y;
45 while(T--){
46 scanf("%d%d",&x,&y);
47 if(x>1000||y>1000){work_1(x,y);continue;}
48 BigInt Fir,Sec;
49 Fir.a[0]=Fir.a[1]=1;
50 Sec.a[0]=Sec.a[1]=1;
51 for(register int i=1;i<=y;++i) Fir=Fir*x;
52 for(register int i=1;i<=y;++i) Sec=Sec*i;
53 //Fir.print();puts("");Sec.print();
54 if(cmp(Fir,Sec)) puts("Yes");
55 else puts("No");
56 }
57 fclose(stdin);
58 fclose(stdout);
59 return 0;
60 }
yuuutsu
T2 august：
先考虑暴力，我们一个一个考虑每个位置，暴力每个位置置为零，当到最后k个时，看一下是否都为零，如果是Yes，否则No。
考虑优化这个过程因为是个区间修改，所以考虑差分，我们维护一个差分数组，发现只有在模k相等的位置才会互相影响，所以维护一个sum数组，含义为模k为i的下标的差分数组之和，这样只要看他是否全为0即可。每次修改只需维护一个桶，每次修改两个位置就好。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=2e6+10;
4 int a[N],tong[N];
5 int main(){
6 freopen("august.in","r",stdin);
7 freopen("august.out","w",stdout);
8 int n,k,q,cnt=0;
9 scanf("%d%d%d",&n,&k,&q);
10 for(int i=1;i<=n;++i) scanf("%d",&a[i]);
11 for(int i=1;i<=n+1;++i) tong[i%k]+=(a[i]-a[i-1]);
12 for(int i=0;i<k;++i) if(tong[i]) cnt++;
13 if(cnt) puts("No");
14 else puts("Yes");
15 for(int i=1;i<=q;++i){
16 int pos,w;
17 scanf("%d%d",&pos,&w);
18 if(tong[pos%k]){
19 tong[pos%k]+=w;
20 if(!tong[pos%k]) cnt--;
21 }
22 else{
23 tong[pos%k]+=w;
24 if(tong[pos%k]) cnt++;
25 }
26 ++pos,w*=-1;
27 if(tong[pos%k]){
28 tong[pos%k]+=w;
29 if(!tong[pos%k]) cnt--;
30 }
31 else{
32 tong[pos%k]+=w;
33 if(tong[pos%k]) cnt++;
34 }
35 if(cnt) puts("No");
36 else puts("Yes");
37 }
38 }
august
T3 sagittarius:
考场上一直想如何去掉非LCA的祖先的贡献，没有想出来，看了题解后发现是非常巧妙的差分处理，即我们设出一个新权值$wt[x]=val[x]-val[fa[x]]$，这样就避免了重复贡献，再用新权值乘以他的子树中所有连续区间即可，发现这个东西暴力统计是布星的，所以我们考虑用线段树合并维护每一个区间（这里所说的区间是子树）从左端点开始的最长连续区间，从右端点开始的最长连续区间和区间内的连续子区间数，则$sn[x]=sn[ls[x]]+sn[rs[x]]+rm[ls[x]]*lm[rs[x]]$，$lm$和$rm$的维护分类讨论即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=2e5+10,M=N*50;
4 #define int long long
5 int first[N],nex[N<<1],to[N<<1],tot;
6 int fa[N],d[N],val[N],rk[N],ans,n,a[N],wt[N];
7 int root[M],lm[M],rm[M],sn[M],ls[M],rs[M];
8 void add(int a,int b){
9 to[++tot]=b,nex[tot]=first[a],first[a]=tot;
10 }
11 void update(int p,int l,int r){
12
13 int mid=l+r>>1;
14 if(lm[ls[p]]==mid-l+1) lm[p]=lm[ls[p]]+lm[rs[p]];
15 else lm[p]=lm[ls[p]];
16 if(rm[rs[p]]==r-mid) rm[p]=rm[rs[p]]+rm[ls[p]];
17 else rm[p]=rm[rs[p]];
18 sn[p]=sn[ls[p]]+sn[rs[p]]+lm[rs[p]]*rm[ls[p]];
19 }
20 int merge(int x,int y,int l,int r){
21 if(!x||!y) return x|y;
22 int mid=(l+r)>>1;
23 ls[x]=merge(ls[x],ls[y],l,mid);
24 rs[x]=merge(rs[x],rs[y],mid+1,r);
25 update(x,l,r);
26 return x;
27 }
28 int cnt=0;
29 void insert(int &x,int l,int r,int pos){
30 if(!x) x=++cnt;
31 if(l==r) return lm[x]=1,rm[x]=1,sn[x]=1,void();
32 int mid=(l+r)>>1;
33 if(pos<=mid) insert(ls[x],l,mid,pos);
34 else insert(rs[x],mid+1,r,pos);
35 update(x,l,r);
36 }
37 void dfs(int x){
38 insert(root[x],1,n,rk[x]);
39 wt[x]=val[x]-val[fa[x]];
40 for(int i=first[x];i;i=nex[i]){
41 int y=to[i];
42 if(y==fa[x]) continue;
43 dfs(y);
44 root[x]=merge(root[x],root[y],1,n);
45 }
46 ans+=wt[x]*sn[root[x]];
47 //cout<<"x=="/*<<x<<" ans=="*/<<sn[root[x]]<<endl;
48 }
49 signed main(){
50 freopen("sagittarius.in","r",stdin);
51 freopen("sagittarius.out","w",stdout);
52 scanf("%lld",&n);
53 for(int i=2;i<=n;++i) {
54 scanf("%lld",&fa[i]);
55 add(fa[i],i);
56 add(i,fa[i]);
57 }
58 //for(int i=1;i<=n;++i) cout<<fa[i]<<" ";cout<<endl;
59 for(int i=1;i<=n;++i) scanf("%lld",&a[i]),rk[a[i]]=i;
60 //for(int i=1;i<=n;++i) cout<<rk[i]<<" ";cout<<endl;
61 for(int i=1;i<=n;++i) scanf("%lld",&val[i]);
62 dfs(1);
63 printf("%lld\n",ans);
64 }
sagittarius