T1
简单签到题，考虑一个点从开头移到结尾会减去小于它的数加上大于它的数。所以 \(O(nlogn)\) 求逆序对，然后 \(O(1)\) 计算一个数移到最后的答案。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define ll long long
int n,a[N],sum[N],sh[N];
ll ans,jg;
int lowbit(int x)
{
return x&(-x);
}
ll query(int x)
{
if(x==0)return 0;
ll c=0;
while(x)
{
c+=sh[x];
x-=lowbit(x);
}
return c;
}
void modify(int x,int zhi)
{
while(x<=n)
{
sh[x]+=zhi;
x+=lowbit(x);
}
}
int main()
{
freopen("rotinv.in","r",stdin);
freopen("rotinv.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum[a[i]]++;
for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
for(int i=1;i<=n;i++)
{
ans+=i-1-query(a[i]);
modify(a[i],1);
}
jg=ans;
for(int i=1;i<n;i++)
{
ans-=sum[a[i]-1];
ans+=(sum[n]-sum[a[i]]);
jg+=ans;
}
printf("%lld\n",jg);
return 0;
}
估计100，实得100；
T2
一个还行的题，考虑像处理区间中只出现一次的颜色个数，记录限制它的位置（第一个大于等于它的数），用可持续化线段树维护信息，统计答案即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N],rot[N],s[N],pre[N],cnt,rs[N<<5],ls[N<<5],sum[N<<5],ss[N];
int modify(int l,int r,int zhi,int las)
{
int x=++cnt;
sum[x]=sum[las]+1,rs[x]=rs[las],ls[x]=ls[las];
if(l==r)return x;
int mid=(l+r)>>1;
if(zhi<=mid)ls[x]=modify(l,mid,zhi,ls[las]);
else rs[x]=modify(mid+1,r,zhi,rs[las]);
return x;
}
int query(int x,int l,int r,int lt,int rt)
{
if(r<lt||l>rt||!x)return 0;
if(lt<=l&&rt>=r)
return sum[x];
int mid=(l+r)>>1,ans=0;
if(lt<=mid)ans+=query(ls[x],l,mid,lt,rt);
if(rt>mid)ans+=query(rs[x],mid+1,r,lt,rt);
return ans;
}
int main()
{
freopen("rise.in","r",stdin);
freopen("rise.out","w",stdout);
scanf("%d%d",&n,&m);
int t=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ss[i]=ss[i-1];//ss存限制为0的个数，因为线段树只存了1-r的信息。
while(t&&a[s[t]]<a[i])t--;//等于不能弹！！！
pre[i]=s[t];
if(pre[i]==0)ss[i]+=1;
s[++t]=i;
}
for(int i=1;i<=n;i++)
{
if(pre[i]==0)rot[i]=rot[i-1];//继承上一个点
else rot[i]=modify(1,n,pre[i],rot[i-1]);//修改pre[i]的链
}
for(int i=1;i<=m;i++)
{
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",query(rot[r],1,n,1,l-1)-l+1+ss[r]);//查询1-r中pre[i]<=l-1的个数+0的个数-(l-1)的个数。
}
return 0;
}
/*
5 4
1 3 2 4 2
1 4
2 4
1 3
2 3
*/
估计100，实际0。
错误原因：
- 单调栈等于不应弹出去
- 可持续化线段树数据范围大于O(nlogn)。
T3
存每个点到根正着反着的数模31的值，\(u,v\)路径上可以求出lca之后组合而成。
变成倍增求lca得例题。
#include <bits/stdc++.h>
using namespace std;
const int mod=31,N=1e5+10;
int n,m,tot,d1[N],d2[N],dep[N],f[N][30],hd[N],jz[N*2],go[N*2],nxt[N*2],pw[N],pwf[N];
void dfs(int u,int fa)
{
f[u][0]=fa;dep[u]=dep[fa]+1;
for(int i=1;i<=20;i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=hd[u];i;i=nxt[i])
{
int v=go[i];
if(v==fa)continue;
d1[v]=(jz[i]*pw[dep[u]-1]%mod+d1[u])%mod;
d2[v]=(d2[u]*10%mod+jz[i])%mod;
dfs(v,u);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y)return x;
}
for(int i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];y=f[y][i];
}
}
return f[x][0];
}
int ksm(int x,int y)
{
int ans=1;
while(y)
{
if(y&1)ans=(ans*x)%mod;
y>>=1;
x=x*x%mod;
}
return ans%mod;
}
void add(int x,int y,int z)
{
nxt[++tot]=hd[x];go[tot]=y;jz[tot]=z;hd[x]=tot;
nxt[++tot]=hd[y];go[tot]=x;jz[tot]=z;hd[y]=tot;
}
int main()
{
freopen("seqmod.in","r",stdin);
freopen("seqmod.out","w",stdout);
scanf("%d%d",&n,&m);
pwf[0]=pw[0]=1;
int ny=ksm(10,mod-2);
// printf("%d\n",ny);
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*10%mod,pwf[i]=pwf[i-1]*ny%mod;
for(int i=1;i<n;i++)
{
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
add(u,v,d);
}
dfs(1,0);
for(int i=1;i<=m;i++)
{
int u,v,la,uu,vv;scanf("%d%d",&u,&v);
la=lca(u,v);
uu=(d1[u]-d1[la]+mod)%mod*pwf[dep[la]-1]%mod;
vv=(d2[v]-d2[la]*pw[dep[v]-dep[la]]%mod+mod)%mod;
printf("%d\n",(uu*pw[dep[v]-dep[la]]%mod+vv)%mod);
}
return 0;
}
估计0（没调出来），实得0.
错误原因：
1.ksm写错了（建议全文背诵）