最后一题无语（有序链剖……）
Problem 1. rotinv
题解
Problem 2. rise
题解
Problem 3. seqmod
（神题特此附上两张图！！！）
题解
idy002大神发明了有序链剖。。。然而并不知道。。。 有序链剖（神！！！）
数据结构专题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
const int N = 1000000 + 10;
template<class T>inline void readin(T &resez){
static char ch;
while((ch=getchar())<'0'||ch>'9');resez=ch-48;
while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ch-48;
}
int n;
int a[N+N];
int bit[N*24];
long long ans,cnt;
void build(int pos,int delta) {
for(register int i = pos;i<=n;i+=i&-i)bit[i] += delta;
}
int query(int right){
int rt=0;
for(register int i=right;i;i-=i&-i)rt += bit[i];
return rt;
}
int main() {
freopen("rotinv.in","r",stdin);
freopen("rotinv.out","w",stdout);
readin(n);
for(register int i=1;i<=n;i++) {
readin(a[i]);
a[n+i]=a[i];
}
for(register int i = 1; i <= n; i++ ) {
cnt+=(i-1)-query(a[i]);
build(a[i],+1);
}
for(register int i = n + 1; i <= n + n; i++ ) {
build(a[i-n],-1);
cnt+=n-1-query(a[i]);
cnt-=query(a[i-n]-1);
build(a[i],+1);
ans+=cnt;
}
cout<<ans<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
const int N=500000+10;
template<class T>inline void readin(T &resez){
static char ch;
while((ch=getchar())<'0'||ch>'9');resez=ch-48;
while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ch-48;
}
struct Node{
int left,right,child_left,child_right,maxn;
Node *ch[2];
int find(int h){
if(left==right)return h<maxn;
else return (h<ch[0]->maxn)?ch[0]->find(h)+child_right:ch[1]->find(h);
}
void update(){
maxn=max(ch[0]->maxn,ch[1]->maxn);
child_right=ch[1]->find(ch[0]->maxn);
child_left=ch[0]->child_left+child_right;
}
}pool[N<<1],*point=pool,*root,*a[N];
int n,m,high[N],head,tail,l,r;
Node *build(int left,int right){
Node *node=++point;
node->left=left;
node->right=right;
if(left==right){
node->child_left=1;
node->child_right=0;
node->maxn=high[left];
}else{
int mid=(left+right)>>1;
node->ch[0]=build(left,mid);
node->ch[1]=build(mid+1,right);
node->update();
}
return node;
}
void ask(Node *node,int L,int R){
if(L<=node->left&&node->right<=R){
a[++tail]=node;return;
}
int mid=(node->left+node->right)>>1;
if(L<=mid)ask(node->ch[0],L,R);
if(R>mid)ask(node->ch[1],L,R);
}
int query(int L,int R){
head=1,tail=0;
ask(root,L,R);
int cnt=0,ans=0;
for(register int i=head;i<=tail;i++){
ans+=a[i]->find(cnt);
cnt=max(cnt,a[i]->maxn);
}
return ans;
}
int main(){
freopen("rise.in","r",stdin);
freopen("rise.out","w",stdout);
readin(n),readin(m);
for(register int i=1;i<=n;i++)readin(high[i]);
root=build(1,n);
while(m--){
readin(l),readin(r);
printf("%d\n",query(l,r));
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <cstdio>
#include <iostream>
#include <algorithm>
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;
}