T1 yuuustu：
可以对两边取对数，然后就转化为两个double的比较，时间复杂度$O(n)$
然后我就用神奇0.4骗分水过
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+;
struct BigInt{
int a[];
BigInt(){memset(a,,sizeof(a));a[]=a[]=;}
BigInt friend operator * (BigInt x,int y){
int len=x.a[],las=;
for(register int i=;i<=len;++i){
x.a[i]=x.a[i]*y+las;
las=x.a[i]/;
x.a[i]%=;
if(i==len&&las) ++len;
}
return x.a[]=len,x;
}
void print(){
for(int i=a[];i>=;--i) cout<<a[i];
}
};
inline bool chk(BigInt a,BigInt b){
for(int i=;i<=a.a[];++i) if(a.a[i]!=b.a[i]) return ;
return ;
}
inline bool cmp(BigInt a,BigInt b){//x^y y!
if(a.a[]==b.a[]) if(chk(a,b)) return ;
if(a.a[]^b.a[]) return a.a[]<b.a[];
else{
for(register int i=a.a[];i>=;--i){
if(a.a[i]==b.a[i]) continue;
if(a.a[i]>b.a[i]) return ;
else if(a.a[i]<b.a[i]) return ;
}
}
}
void work_1(int x,int y){
if(x>y*0.4) puts("No");
else puts("Yes");
}
int main(){
freopen("yuuutsu.in","r",stdin);
freopen("yuuutsu.out","w",stdout);
int T;
scanf("%d",&T);register int x,y;
while(T--){
scanf("%d%d",&x,&y);
if(x>||y>){work_1(x,y);continue;}
BigInt Fir,Sec;
Fir.a[]=Fir.a[]=;
Sec.a[]=Sec.a[]=;
for(register int i=;i<=y;++i) Fir=Fir*x;
for(register int i=;i<=y;++i) Sec=Sec*i;
//Fir.print();puts("");Sec.print();
if(cmp(Fir,Sec)) puts("Yes");
else puts("No");
}
fclose(stdin);
fclose(stdout);
return ;
}
yuuutsu
T2 august：
先考虑暴力，我们一个一个考虑每个位置，暴力每个位置置为零，当到最后k个时，看一下是否都为零，如果是Yes，否则No。
考虑优化这个过程因为是个区间修改，所以考虑差分，我们维护一个差分数组，发现只有在模k相等的位置才会互相影响，所以维护一个sum数组，含义为模k为i的下标的差分数组之和，这样只要看他是否全为0即可。每次修改只需维护一个桶，每次修改两个位置就好。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+;
int a[N],tong[N];
int main(){
freopen("august.in","r",stdin);
freopen("august.out","w",stdout);
int n,k,q,cnt=;
scanf("%d%d%d",&n,&k,&q);
for(int i=;i<=n;++i) scanf("%d",&a[i]);
for(int i=;i<=n+;++i) tong[i%k]+=(a[i]-a[i-]);
for(int i=;i<k;++i) if(tong[i]) cnt++;
if(cnt) puts("No");
else puts("Yes");
for(int i=;i<=q;++i){
int pos,w;
scanf("%d%d",&pos,&w);
if(tong[pos%k]){
tong[pos%k]+=w;
if(!tong[pos%k]) cnt--;
}
else{
tong[pos%k]+=w;
if(tong[pos%k]) cnt++;
}
++pos,w*=-;
if(tong[pos%k]){
tong[pos%k]+=w;
if(!tong[pos%k]) cnt--;
}
else{
tong[pos%k]+=w;
if(tong[pos%k]) cnt++;
}
if(cnt) puts("No");
else puts("Yes");
}
}
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$的维护分类讨论即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+,M=N*;
#define int long long
int first[N],nex[N<<],to[N<<],tot;
int fa[N],d[N],val[N],rk[N],ans,n,a[N],wt[N];
int root[M],lm[M],rm[M],sn[M],ls[M],rs[M];
void add(int a,int b){
to[++tot]=b,nex[tot]=first[a],first[a]=tot;
}
void update(int p,int l,int r){ int mid=l+r>>;
if(lm[ls[p]]==mid-l+) lm[p]=lm[ls[p]]+lm[rs[p]];
else lm[p]=lm[ls[p]];
if(rm[rs[p]]==r-mid) rm[p]=rm[rs[p]]+rm[ls[p]];
else rm[p]=rm[rs[p]];
sn[p]=sn[ls[p]]+sn[rs[p]]+lm[rs[p]]*rm[ls[p]];
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x|y;
int mid=(l+r)>>;
ls[x]=merge(ls[x],ls[y],l,mid);
rs[x]=merge(rs[x],rs[y],mid+,r);
update(x,l,r);
return x;
}
int cnt=;
void insert(int &x,int l,int r,int pos){
if(!x) x=++cnt;
if(l==r) return lm[x]=,rm[x]=,sn[x]=,void();
int mid=(l+r)>>;
if(pos<=mid) insert(ls[x],l,mid,pos);
else insert(rs[x],mid+,r,pos);
update(x,l,r);
}
void dfs(int x){
insert(root[x],,n,rk[x]);
wt[x]=val[x]-val[fa[x]];
for(int i=first[x];i;i=nex[i]){
int y=to[i];
if(y==fa[x]) continue;
dfs(y);
root[x]=merge(root[x],root[y],,n);
}
ans+=wt[x]*sn[root[x]];
//cout<<"x=="/*<<x<<" ans=="*/<<sn[root[x]]<<endl;
}
signed main(){
freopen("sagittarius.in","r",stdin);
freopen("sagittarius.out","w",stdout);
scanf("%lld",&n);
for(int i=;i<=n;++i) {
scanf("%lld",&fa[i]);
add(fa[i],i);
add(i,fa[i]);
}
//for(int i=1;i<=n;++i) cout<<fa[i]<<" ";cout<<endl;
for(int i=;i<=n;++i) scanf("%lld",&a[i]),rk[a[i]]=i;
//for(int i=1;i<=n;++i) cout<<rk[i]<<" ";cout<<endl;
for(int i=;i<=n;++i) scanf("%lld",&val[i]);
dfs();
printf("%lld\n",ans);
}
sagittarius