远在上海的的idy002写的学报，这篇报告，是呼应那篇报告的。
1.rotinv
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> using namespace std; const int N=100010 using namespace std; int later[N]; int a[N]; int main() { int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if (a[j]>a[i]) { later[i]=j; break; } while(q--) { int l,r; scanf("%d%d",&l,&r); int p=l; int tot=0; while(p<=r&&p!=0)//这里从l开始，依据预处理的路径来计数 { tot++; p=later[p]; } printf("%d\n",tot); } }【解题报告】 这道题是这样一个思路： 首先我们需要将[1,n]的数组开一个镜像，在[n+1,2n]的空间存储相同的内容。我们先算出[1,n]之内的逆序对个数，之后将这个区间向右移动，算出这个新的区间的逆序对个数（这样做就可以穷尽所有的组合情况），之后输出就可以了。 那么我们用什么办法算出一个区间的逆序对个数呢？我们从左到右枚举每一个数，找出比这个数大的数累加个数就可以了。 那么怎么维护这样一个区间的答案呢？我们算出了[i,j]过后，右移一位即是[i+1,j+1]，我们只需要把[i+1,j]中比a[j+1]大的数，再减去[i+1,j]中比a[i]小的个数（实质上就是把比原来的右端点小的减去，把比现在的右端点大的加上）。再把这样一个值同[i,j]的值加起来。 此外再用树状数组优化。 来看看代码：
2.rise
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> using namespace std; const int N=1000000+10; int n; int a[N+N]; int bit[N*24]; long long ans,cnt; void build(int pos,int delta)//在树状数组中添加 { for(int i=pos;i<=n;i+=i&-i) bit[i]+=delta; } int query(int right)//树状数组中求和 { int rt=0; for(int i=right;i;i-=i&-i) rt+=bit[i]; return rt; } 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]); a[n+i]=a[i]; } for(int i=1;i<=n;i++) { cnt+=(i-1)-query(a[i]); build(a[i],+1); }//这时cnt中存储的是[1,n]中的逆序对个数 for(int i=n+1;i<=n+n;i++)//这里就将a[1,n]的区间向右移，修改cnt的值，使其负荷情况 { build(a[i-n],-1); cnt+=n-1-query(a[i]); cnt-=query(a[i-n]-1); build(a[i],+1); ans+=cnt; } printf("%d",ans); return 0; }【解题报告】 这道题有两种解法，一种是用线段树（此处略），另一种是通过搞一个类似于“链表”的结构，将某一柱子向右离他最近的那个柱子标记好。最后查询时按照我构造的这个路径即可。
3、
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> using namespace std; const int N=100000 + 10; const int M=N<<1; const int Mod=31; template<class T>inline void readin(T &res){ static char ch; while((ch=getchar())<'0'||ch>'9');res=ch-48; while((ch=getchar())<='9'&&ch>='0')res=res*10+ch-48; } struct Point{ int v,len; Point(){} Point(int v,int len):v(v),len(len){} }; int head[N],wght[M],dest[M],last[M],etot; int depf[N],siz[N],son[N],top[N],father[N],val[N],in[N],rank[N],deps[N],pos_id; struct Node{ Point ab,ba; Node *ls,*rs; }point_pool[N*4],*tail=point_pool,*root; void init(){ deps[0]=1; for(register int i=1;i<N;i++) deps[i]=deps[i-1]*10%Mod; } Point link(const Point &a,const Point &b){ return Point((a.v * deps[b.len] + b.v) % Mod,a.len + b.len); } Node *build(int lf,int rg){ Node *nd=++tail; if(lf == rg){ nd->ab=nd->ba=Point(val[rank[lf]],1); } else{ int mid=(lf + rg)>>1; nd->ls=build(lf,mid); nd->rs=build(mid + 1,rg); nd->ab=link(nd->ls->ab,nd->rs->ab); nd->ba=link(nd->rs->ba,nd->ls->ba); } return nd; } Point query_ab(Node *nd,int lf,int rg,int L,int R){ if(L <= lf && rg <= R) return nd->ab; int mid=(lf + rg)>>1; if(R <= mid) return query_ab(nd->ls,lf,mid,L,R); else if(L>mid) return query_ab(nd->rs,mid+1,rg,L,R); else return link( query_ab(nd->ls,lf,mid,L,R), query_ab(nd->rs,mid+1,rg,L,R)); } Point query_father(Node *nd,int lf,int rg,int L,int R){ if(L <= lf && rg <= R) return nd->ba; int mid=(lf + rg)>>1; if(R <= mid) return query_father(nd->ls,lf,mid,L,R); else if(L>mid) return query_father(nd->rs,mid+1,rg,L,R); else return link( query_father(nd->rs,mid+1,rg,L,R), query_father(nd->ls,lf,mid,L,R)); } void adde(int u,int v,int d){ etot++; dest[etot]=v; last[etot]=head[u]; wght[etot]=d; head[u]=etot; } void dfs1(int u){ siz[u]=1; for(register int t=head[u]; t; t=last[t]){ int v=dest[t]; if(v == father[u]) continue; father[v]=u; depf[v]=depf[u] + 1; val[v]=wght[t]; dfs1(v); siz[u] += siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u){ in[u]=++pos_id; rank[pos_id]=u; if(son[u]){ top[son[u]]=top[u]; dfs2(son[u]); } for(register int t=head[u]; t; t=last[t]){ int v=dest[t]; if(v == father[u] || v == son[u]) continue; top[v]=v; dfs2(v); } } int query(int u,int v){ Point y_x(0,0),x_y(0,0); while(top[u]!=top[v]){ if(depf[top[u]]>depf[top[v]]){ y_x=link(y_x,query_father(root,1,pos_id,in[top[u]],in[u])); u=father[top[u]]; } else{ x_y=link(query_ab(root,1,pos_id,in[top[v]],in[v]),x_y); v=father[top[v]]; } } if(depf[u]>depf[v]){ y_x=link(y_x,query_father(root,1,pos_id,in[v]+1,in[u])); } else if(depf[v]>depf[u]){ x_y=link(query_ab(root,1,pos_id,in[u]+1,in[v]),x_y); } Point ans=link(y_x,x_y); return ans.v; } int n,m; int main(){ freopen("seqmod.in","r",stdin); freopen("seqmod.out","w",stdout); readin(n),readin(m); for(register int i=1;i<n;i++){ int u,v,d; readin(u),readin(v),readin(d), adde(u,v,d); adde(v,u,d); } init(); father[1]=1; depf[1]=0; dfs1(1); top[1]=1; dfs2(1); root=build(1,pos_id); while(m--){ int u,v; readin(u),readin(v); printf("%d\n",query(u,v)); } return 0; }2017.3.22
