ACM

One,Two,Three,Ak模板

Posted by Cww97 on 2018-09-26

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/82855060
# East China Normal University

队名
队名

Team’s Name

Chinese:道生一,一生二,二生三,三生万物

English:One,Two,Three,AK

Members

XuLiang Zhu - Mathematics

Mengyun Chen - Computer Science

Jiadong Xie - Software Engineering

文章目录

对拍

建立一个 test.sh 的文件

1
2
3
4
5
6
7
While true; do
./maker
./a
./b
if diff 1.out 2.out; then echo “AC”;else break;
fi
done

终端编译命令

1
2
chmod +x test.sh
./test.sh

输入输出优化

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
#define LL long long  

using namespace std;

inline char nc(){
/*
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
*/return getchar();
}

inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(char &x){
for (x=nc();!(x=='('||x==')');x=nc());
}

inline int read(char *s)
{
char c=nc();int len=1;
for(;!(c=='('||c==')');c=nc()) if (c==EOF) return 0;
for(;(c=='('||c==')');s[len++]=c,c=nc());
s[len++]='\0';
return len-2;
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

数据结构

hash

常用质数

1572869, 3145739, 6291469, 12582917, 25165843, 50331653
7881299347898369 原根 6
180143985094819841 原根 6
1945555039024054273 原根 5
4179340454199820289 原根 3

字符串哈希

不同长度的字符串哈希,需要加一维长度。

二维hash

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
#define seed 13131
#define seed1 1313
#define maxn 1005
typedef unsigned long long ull;
using namespace std;
ull p,Hash[maxn][maxn],Hash1[maxn][maxn];
char s[maxn][maxn],str[105][105];
int n,m,x,y;
ull getHash()
{
ull a,b=0;
for(int i=0;i<x;i++)
{
a=0;
for(int j=0;j<y;j++)
a=a*seed1+str[i][j];
b=b*seed+a;
}
return b;
}
int getAns()
{
ull base,a;
int ans=0;
base=1;
for(int i=0;i<y;i++)
base*=seed1;
for(int i=0;i<n;i++)
{
a=0;
for(int j=0;j<y;j++)
a=a*seed1+s[i][j];
Hash1[i][y-1]=a;
for(int j=y;j<m;j++)
Hash1[i][j]=Hash1[i][j-1]*seed1-s[i][j-y]*base+s[i][j];
}
base=1;
for(int i=0;i<x;i++)
base*=seed;
for(int i=y-1;i<m;i++)
{
a=0;
for(int j=0;j<x;j++)
a=a*seed+Hash1[j][i];
Hash[x-1][i]=a;
if(a==p) ans++;
for(int j=x;j<n;j++)
{
Hash[j][i]=Hash[j-1][i]*seed-Hash1[j-x][i]*base+Hash1[j][i];
if(Hash[j][i]==p) ans++;
}
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",s[i]);
scanf("%d%d",&x,&y);
for(int i=0;i<x;i++)
scanf("%s",str[i]);
p=getHash(); //hash str
printf("%d\n",getAns()); //hash s
}
return 0;
}

并查集

1
2
3
4
5
6
7
8
9
10
int Find(int x)
{
return x==fa[x]?x:fa[x]=Find(fa[x]);
}

int main()
{
p=Find(id[x]),q=Find(id[y]);
fa[p]=q;
}

可持久化并查集

修改操作(镜像)

1 p q:合并p和q所在集合,如果已经在一个集合中,忽略此命令
2 p q:把p移动到q所在集合,如果已经在一个集合中,忽略此命令
3 p:输出p所在集合的元素个数和该集合所有元素之和

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
const int MAXN = 100010;
int n,m;
int father[MAXN];
int sum[MAXN],num[MAXN];
void init(){
for(int i=1;i<=n;i++){
father[i]=i+n;
father[i+n]=i+n;
sum[i+n]=i;
num[i+n]=1;
}
}
int find(int x){
return father[x]!=x?father[x]=find(father[x]):x;
}
int main(){
int mark,x,y;
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(register int i=0;i<m;i++){
scanf("%d",&mark);
if(mark==1){
scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
if(fx!=fy){
father[fx]=fy;
sum[fy]+=sum[fx];
num[fy]+=num[fx];
}
}else if(mark==2){
scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
if(fx!=fy){
father[x]=fy;
sum[fy]+=x,sum[fx]-=x;
num[fy]++,num[fx]--;
}
}else{
scanf("%d",&x);
int fx=find(x);
printf("%d %d\n",num[fx],sum[fx]);
}
}
}
return 0;
}

历史查询

1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出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
#define N 2000005
int n,m,sz;
int root[N],ls[N],rs[N],v[N],deep[N];
void build(int &k,int l,int r){
if(!k)k=++sz;
if(l==r){v[k]=l;return;}
int mid=(l+r)>>1;
build(ls[k],l,mid);
build(rs[k],mid+1,r);
}
void modify(int l,int r,int x,int &y,int pos,int val){
y=++sz;
if(l==r){v[y]=val;deep[y]=deep[x];return;}
ls[y]=ls[x];rs[y]=rs[x];
int mid=(l+r)>>1;
if(pos<=mid)
modify(l,mid,ls[x],ls[y],pos,val);
else modify(mid+1,r,rs[x],rs[y],pos,val);
}
int query(int k,int l,int r,int pos){
if(l==r)return k;
int mid=(l+r)>>1;
if(pos<=mid)return query(ls[k],l,mid,pos);
else return query(rs[k],mid+1,r,pos);
}
void add(int k,int l,int r,int pos){
if(l==r){deep[k]++;return;}
int mid=(l+r)>>1;
if(pos<=mid)add(ls[k],l,mid,pos);
else add(rs[k],mid+1,r,pos);
}
int find(int k,int x){
int p=query(k,1,n,x);
return x==v[p]?p:find(k,v[p]);
}
int main(){
int f,k,a,b;
cin>>n>>m;
build(root[0],1,n);
for(register int i=1;i<=m;i++){
cin>>f;
if(f==1){
root[i]=root[i-1];
cin>>a>>b;
int p=find(root[i],a),q=find(root[i],b);
if(v[p]==v[q])continue;
if(deep[p]>deep[q])swap(p,q);
modify(1,n,root[i-1],root[i],v[p],v[q]);
if(deep[p]==deep[q])add(root[i],1,n,v[q]);
}else if(f==2){
cin>>k;root[i]=root[k];
}else if(f==3){
root[i]=root[i-1];
cin>>a>>b;
int p=find(root[i],a),q=find(root[i],b);
if(v[p]==v[q])cout<<1<<endl;
else cout<<0<<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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5;
int fa[N],rnk[N];
void Init(int n)
{
for(int i=0;i<=n;i++)
{
fa[i]=i;
rnk[i]=0;
}
}
int Find(int x)
{
if(x==fa[x])return x;
int temp=fa[x];
fa[x]=Find(fa[x]);
rnk[x]=rnk[x]+rnk[temp];
return fa[x];
}
void Merge(int s,int x,int y)
{
int rx=Find(x);
int ry=Find(y);
if(rx==ry)return ;
fa[rx]=ry;
rnk[rx]=s+rnk[y]-rnk[x];
}
int main()
{
int n,m,q;
cin>>n>>m>>q; //人数,关系数,询问数
Init(n);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c); //a比b高c分
Merge(c,a,b);
}
while(q--)
{
int a,b;
scanf("%d%d",&a,&b); //想知道a号同学的分数比b号同学的分数高几分
int ra=Find(a);
int rb=Find(b);
if(ra!=rb)printf("-1\n");
else printf("%d\n",rnk[a]-rnk[b]);
}
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
const int N=100005;
int n,m,a[4*N];
LL tr[4*N],add[4*N],mul[4*N],p;

void update(int x)
{
tr[x]=(tr[x<<1]+tr[x<<1|1])%p;
}

void build(int now,int l,int r)
{
mul[now]=1;add[now]=0;
if (l==r){tr[now]=a[l];mul[now]=1;return;}
int mid=l+r>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
update(now);
}

void pushdown(int now,int l,int r)
{
int mid=l+r>>1;
if (mul[now]!=1)
{
tr[now<<1]=tr[now<<1]*mul[now]%p;
tr[now<<1|1]=tr[now<<1|1]*mul[now]%p;
mul[now<<1]=mul[now<<1]*mul[now]%p;
mul[now<<1|1]=mul[now<<1|1]*mul[now]%p;
add[now<<1]=add[now<<1]*mul[now]%p;
add[now<<1|1]=add[now<<1|1]*mul[now]%p;
mul[now]=1;
}
if (add[now])
{
tr[now<<1]+=add[now]*(mid-l+1)%p;
if (tr[now]>=p) tr[now]-=p;
tr[now<<1|1]+=add[now]*(r-mid)%p;
if (tr[now]>=p) tr[now]-=p;
add[now<<1]+=add[now];
if (add[now]>=p) add[now]-=p;
add[now<<1|1]+=add[now];
if (add[now]>=p) add[now]-=p;
add[now]=0;
}
}

void qjmul(int now,int l,int r,int ll,int rr,LL val)
{
if (ll<=l&&r<=rr)
{
tr[now]=tr[now]*val%p;
mul[now]=mul[now]*val%p;
add[now]=add[now]*val%p;
return;
}
int mid=l+r>>1;
pushdown(now,l,r);
if (ll<=mid) qjmul(now<<1,l,mid,ll,rr,val);
if (rr>mid) qjmul(now<<1|1,mid+1,r,ll,rr,val);
update(now);
}

void qjadd(int now,int l,int r,int ll,int rr,LL val)
{
if (ll<=l&&r<=rr)
{
tr[now]=(LL)(tr[now]+(LL)(r-l+1)*val%p);
if (tr[now]>=p) tr[now]-=p;
add[now]+=val;
if (add[now]>=p) add[now]-=p;
return;
}
int mid=l+r>>1;
pushdown(now,l,r);
if (ll<=mid) qjadd(now<<1,l,mid,ll,rr,val);
if (rr>mid) qjadd(now<<1|1,mid+1,r,ll,rr,val);
update(now);
}

LL qjsum(int now,int l,int r,int ll,int rr)
{
if (ll<=l&&r<=rr) return tr[now];
int mid=l+r>>1; LL ans=0;
pushdown(now,l,r);
if (ll<=mid) ans+=qjsum(now<<1,l,mid,ll,rr); ans%=p;
if (rr>mid) ans+=qjsum(now<<1|1,mid+1,r,ll,rr); ans%=p;
return ans;
}

int main()
{
read(n),read(m),read(p);
for (int i=1;i<=n;i++)
read(a[i]);
build(1,1,n);
for (int i=1;i<=m;i++)
{
int opt,x,y,z;
read(opt);read(x);read(y);
if (opt==2) read(z),qjadd(1,1,n,x,y,z);
if (opt==1) read(z),qjmul(1,1,n,x,y,z);
if (opt==3) print(qjsum(1,1,n,x,y)%p),puts("");
}
return 0;
}

区间覆盖,询问

1 a:询问是不是有连续长度为 a 的空房间,有的话住进最左边
2 a b:将[a,a+b-1]的房间清空

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
struct ST
{
int l,r,lc,rc,lf,rf,f,flag;
}a[200010];
int n,m;

void build(int l,int r,int x)
{
a[x].l=l,a[x].r=r;a[x].flag=0;
a[x].lf=a[x].rf=a[x].f=r-l+1;
if (l==r) {a[x].lc=a[x].rc=0;return ;}
int mid=(l+r)>>1;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
a[x].lc=x*2;a[x].rc=x*2+1;
}

void Pushdown(int x)
{
if (a[x].flag==1)
{
a[x].flag=0;
a[a[x].lc].f=a[a[x].lc].lf=a[a[x].lc].rf=0;
if (a[a[x].lc].r!=a[a[x].lc].l) a[a[x].lc].flag=1;
a[a[x].rc].f=a[a[x].rc].lf=a[a[x].rc].rf=0;
if (a[a[x].rc].r!=a[a[x].rc].l) a[a[x].rc].flag=1;
}
if (a[x].flag==-1)
{
a[x].flag=0;
a[a[x].lc].f=a[a[x].lc].lf=a[a[x].lc].rf=a[a[x].lc].r-a[a[x].lc].l+1;
if (a[a[x].lc].r!=a[a[x].lc].l) a[a[x].lc].flag=-1;
a[a[x].rc].f=a[a[x].rc].lf=a[a[x].rc].rf=a[a[x].rc].r-a[a[x].rc].l+1;
if (a[a[x].rc].r!=a[a[x].rc].l) a[a[x].rc].flag=-1;
}
}

int query(int k,int x)
{
if (a[x].lf>=k) return a[x].l;
Pushdown(x);
if (a[a[x].lc].f>=k) return query(k,a[x].lc);
if (a[a[x].lc].rf+a[a[x].rc].lf>=k) return a[a[x].lc].r-a[a[x].lc].rf+1;
return query(k,a[x].rc);
}

void change(int l,int r,int x,int z)
{
if (l<=a[x].l && r>=a[x].r)
{
if (a[x].l==a[x].r)
{
if (z==1) a[x].f=a[x].rf=a[x].lf=0;
else a[x].f=a[x].rf=a[x].lf=1;
}
else
{
if (z==1) a[x].flag=1,a[x].f=a[x].lf=a[x].rf=0;
else a[x].flag=-1,a[x].f=a[x].lf=a[x].rf=a[x].r-a[x].l+1;
}
return ;
}
Pushdown(x);
int mid=(a[x].l+a[x].r)>>1;
if (l<=mid) change(l,r,x*2,z);
if (r>mid) change(l,r,x*2+1,z);
a[x].f=max(a[a[x].lc].f,a[a[x].rc].f);
a[x].f=max(a[x].f,a[a[x].lc].rf+a[a[x].rc].lf);
if (a[a[x].lc].lf==a[a[x].lc].r-a[a[x].lc].l+1) a[x].lf=a[a[x].lc].lf+a[a[x].rc].lf;
else a[x].lf=a[a[x].lc].lf;
if (a[a[x].rc].rf==a[a[x].rc].r-a[a[x].rc].l+1) a[x].rf=a[a[x].rc].rf+a[a[x].lc].rf;
else a[x].rf=a[a[x].rc].rf;
}

int main()
{
read(n);read(m);
build(1,n,1);
int x,y;
while (m--)
{
read(x);
if (x==1)
{
read(y);
if (a[1].f<y) print(0),putchar('\n');
else
{
int ans=query(y,1);
print(ans),putchar('\n');
change(ans,ans+y-1,1,1);
}
}
else
{
read(x);read(y);
change(x,x+y-1,1,-1);
}
}
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
#define maxn 50010
int T,n,m;
double ans;
char s[50];
struct ST
{
double k,b;
bool flag;
}tree[4*maxn];

double cross(double k1,double b1,double k2,double b2) //计算交点(需要注意斜率相等的情况)
{
return (b2-b1)/(1.0*(k1-k2));
}

void Insert(int x,int l,int r,double B,double K)
{
if (!tree[x].flag) {tree[x].k=K,tree[x].b=B,tree[x].flag=1;return;}
int mid=l+r>>1;
double f1=1.0*K*l+B,f2=1.0*tree[x].k*l+tree[x].b,f3=1.0*K*r+B,f4=1.0*tree[x].k*r+tree[x].b;
if (f1<=f2&&f3<=f4) return;
if (f1>=f2&&f3>=f4) {tree[x].k=K,tree[x].b=B;return;}
double xx=cross(K,B,tree[x].k,tree[x].b);
if (f1>=f2)
{
if (xx<=mid) Insert(x<<1,l,mid,B,K);
else Insert(x<<1|1,mid+1,r,tree[x].b,tree[x].k),tree[x].k=K,tree[x].b=B;
}
else
{
if (xx>mid) Insert(x<<1|1,mid+1,r,B,K);
else Insert(x<<1,l,mid,tree[x].b,tree[x].k),tree[x].k=K,tree[x].b=B;
}
}

void query(int x,int l,int r,int q)
{
if (tree[x].flag) ans=max(ans,1.0*tree[x].k*q+tree[x].b); //这里不能return,要走到底
if (l==r) return ;
int mid=l+r>>1;
if (q<=mid)query(x<<1,l,mid,q);else query(x<<1|1,mid+1,r,q);
}

int main()
{
n=50000;
read(T);
while (T--)
{
int x=read(s);double B,K;
if (s[1]=='P') scanf("%lf%lf",&B,&K),Insert(1,1,n,B-K,K); //一次函数第一天为B,公差为K
else read(x),ans=0,query(1,1,n,x),print((LL)floor(ans/100.0)),puts(""); //询问第x天函数max
}
return 0;
}

线段树的合并

求子树中有几个节点的权值小于根结点的权值

dfs,回溯的时候合并子树所构成的线段树

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
const int N=100010,M=N*20;
int n,a[N],ans[N],root[N],disc[N];
vector<int> v[N];
namespace Segment_Tree{
int tot;
struct node{int l,r,a,b,sum;}T[M];
void up(int x){T[x].sum=T[T[x].l].sum+T[T[x].r].sum;}
int build(int l,int r,int p){
int x=++tot;
T[x].a=l; T[x].b=r; T[x].sum=0;
if(l==r){T[x].sum=1;return x;}
int mid=(l+r)>>1;
if(p<=mid){T[x].l=build(l,mid,p);}
else{T[x].r=build(mid+1,r,p);}
return up(x),x;
}
int ask(int x,int l,int r){
if(!x)return 0;
if(l<=T[x].a&&T[x].b<=r)return T[x].sum;
int mid=(T[x].a+T[x].b)>>1,res=0;
if(l<=mid)res+=ask(T[x].l,l,r);
if(r>mid)res+=ask(T[x].r,l,r);
return res;
}
int merge(int x,int y){
if(!x||!y)return x^y;
T[x].l=merge(T[x].l,T[y].l);
T[x].r=merge(T[x].r,T[y].r);
return up(x),x;
}
void dfs(int x,int fx){
int res=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fx)continue;
dfs(y,x);
res+=ask(root[y],a[x]+1,n);
root[x]=merge(root[x],root[y]);
}ans[x]=res;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),disc[i]=a[i];
sort(disc+1,disc+n+1);
int m=unique(disc+1,disc+n+1)-disc-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(disc+1,disc+m+1,a[i])-disc;
for(int i=2;i<=n;i++){
int x; scanf("%d",&x);
v[x].push_back(i); v[i].push_back(x);
}
for(int i=1;i<=n;i++)root[i]=Segment_Tree::build(1,n,a[i]);
Segment_Tree::dfs(1,1);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}

线段树合并与拆分

1:(0,l,r)表示将区间[l,r]的数字升序排序

2:(1,l,r)表示将区间[l,r]的数字降序排序

最后询问第q位置上的数字。

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
#include<iostream>  
#include<queue>
using namespace std;
#define mid ((l+r)>>1)
#define ls t<<1,l,mid
#define rs t<<1|1,mid+1,r
#define ND 2000010
#define mxn 100010
int n,m,k,x,tt,val,i,last,op,L,R,now,nxt,LEFT,RIGHT;
struct data{
int l,r,tp,nxt;
}c[ND];
struct segment_tree{
struct data{
bool exi;
int rmax;
}a[mxn<<2];
void update(int t){
a[t]=(data){
a[t<<1].exi||a[t<<1|1].exi,
a[t<<1|1].rmax?a[t<<1|1].rmax:a[t<<1].rmax
};
}
void ins(int t,int l,int r){
if (l==r) a[t]=(data){k?1:0,k}; else
if (x<=mid) ins(ls),update(t); else
ins(rs),update(t);
}
int ask(int t,int l,int r){
if (l>x||(!a[t].exi)) return 0;
if (l==r) return a[t].rmax;
return (tt=ask(rs))?tt:(mid<=x?a[t<<1].rmax:ask(ls));
}
}T;
queue <int> q;
int newnode(){
int k=q.front();
q.pop();
return k;
}
struct node{
int l,r,sum;
}a[ND];
void clear(int t){
a[t]=a[0];
q.push(t);
}
void build(int t,int l,int r){
a[t].sum=1;
if (l==r) return;
if (val<=mid) build(a[t].l=newnode(),l,mid);
else build(a[t].r=newnode(),mid+1,r);
}
int merge(int t1,int t2){
if (t1==0||t2==0) return t1+t2;
a[t1].l=merge(a[t1].l,a[t2].l);
a[t1].r=merge(a[t1].r,a[t2].r);
a[t1].sum+=a[t2].sum;
clear(t2);
return t1;
}
void split(int t1,int t2,int k){
int tt=a[a[t1].l].sum;
if (k>tt) split(a[t1].r,a[t2].r=newnode(),k-tt); else swap(a[t2].r,a[t1].r);
if (k<tt) split(a[t1].l,a[t2].l=newnode(),k);
a[t2].sum=a[t1].sum-k;
a[t1].sum=k;
}
int ask(int t,int l,int r,int k){
if (l==r) return l;
int tt=a[a[t].l].sum;
if (k>tt) return ask(a[t].r,mid+1,r,k-tt);
else return ask(a[t].l,l,mid,k);
}
int main(){
for (i=1;i<=ND-10;i++)q.push(i);
cin>>n>>m;
for (x=1,last=ND-5;x<=n;last=k,x++){
cin>>val;
c[k=c[last].nxt=newnode()]=(data){x,x,0,0};
T.ins(1,1,n);
build(k,1,n);
}
while (m--){
cin>>op>>L>>R;
x=L;
LEFT=T.ask(1,1,n);
if (L==c[LEFT].l){
RIGHT=newnode();
swap(a[RIGHT],a[LEFT]);
swap(c[RIGHT],c[LEFT]);
c[now=LEFT]=(data){L,R,op,RIGHT};
} else{
c[now=newnode()]=(data){L,R,op,RIGHT=newnode()};
if (!c[LEFT].tp) split(LEFT,RIGHT,L-c[LEFT].l);
else split(LEFT,RIGHT,c[LEFT].r-L+1),swap(a[LEFT],a[RIGHT]);
c[RIGHT]=c[LEFT];
c[RIGHT].l=L;
c[LEFT].r=L-1;
c[LEFT].nxt=now;
}
for (nxt=RIGHT;nxt&&R>=c[nxt].r;last=nxt,nxt=c[nxt].nxt,c[last]=c[0]){
merge(now,nxt);
x=c[nxt].l,k=0;
T.ins(1,1,n);
}
c[now].nxt=nxt;
if (nxt!=0&&c[nxt].l<=R){
x=c[nxt].l,k=0;
T.ins(1,1,n);
if (c[nxt].tp) split(nxt,tt=newnode(),c[nxt].r-R);
else split(nxt,tt=newnode(),R-c[nxt].l+1),swap(a[nxt],a[tt]);
merge(now,tt);
x=c[nxt].l=R+1;
k=nxt;
T.ins(1,1,n);
}
x=L,k=now;
T.ins(1,1,n);
}
cin>>x;
now=T.ask(1,1,n);
if (c[now].tp) cout<<ask(now,1,n,c[now].r-x+1)<<"\n";
else cout<<ask(now,1,n,x-c[now].l+1)<<"\n";
return 0;
}

权值线段树中位数查询

离散化后一共有 m 个元素,支持以下操作:

1.ins c d e:插入一个离散化后是 c 的元素,对 cnt 的贡献为 d,对 sum 的贡献为 e。

2.ask:查询所有数字与中位数的差值的绝对值的和。

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
struct ST
{
int v[N];LL sum[N];
void ins(int c,int d,int e)
{
int a=1,b=m,x=1,mid;
while(1)
{
v[x]+=d,sum[x]+=e;
if(a==b)return;
x<<=1;
if(c<=(mid=(a+b)>>1))b=mid;else x|=1,a=mid+1;
}
}
LL ask()
{
if(v[1]<=1)return 0;
int a=1,b=m,mid,t,k=(v[1]+1)/2,x=1,cnt=0;LL ans=0;
while(a<b)
{
mid=(a+b)>>1,t=v[x<<=1];
if(k<=t)cnt+=v[x|1],ans+=sum[x|1],b=mid;
else cnt−=t,ans−=sum[x],k−=t,a=mid+1,x|=1;
}
return ans−sum[x]/v[x]*cnt;
}
};

二维线段树

1.将子矩阵x1,y1,x2,y2所有元素加上V

2.将子矩阵x1,y1,x2,y2所有元素设为V

3查询将子矩阵x1,y1,x2,y2的和,最大,小值

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#define inf 0x3f3f3f3f
int ans,MX,MN;
#define lson L,mid,(rt<<1)
#define rson mid+1,R,(rt<<1|1)
struct point
{
int lc,rc,sum,mx,mn,add,set;
int mid(){return (lc+rc)>>1;}
};
point **tree;
void init(int r,int c)
{
tree=new point*[r+1];
for(int i=0;i<=r;i++)
{
tree[i]=new point[c*4];
}
}
void deal(int r,int c)
{
for(int i=0;i<=r;i++)
{
delete tree[i];
}
delete tree;
}
void pushup(int r,int rt)
{
tree[r][rt].sum=tree[r][rt<<1].sum+tree[r][rt<<1|1].sum;
tree[r][rt].mx=max(tree[r][rt<<1].mx,tree[r][rt<<1|1].mx);
tree[r][rt].mn=min(tree[r][rt<<1].mn,tree[r][rt<<1|1].mn);
}
void pushdown(int r,int rt)
{
int lg=tree[r][rt].rc-tree[r][rt].lc+1;
int rset,radd;
rset=tree[r][rt].set;
radd=tree[r][rt].add;
if(tree[r][rt].set)
{
tree[r][rt<<1].sum=rset*(lg-(lg>>1));
tree[r][rt<<1|1].sum=rset*(lg>>1);

tree[r][rt<<1].mx=rset;
tree[r][rt<<1].mn=rset;
tree[r][rt<<1|1].mx=rset;
tree[r][rt<<1|1].mn=rset;

tree[r][rt<<1].set=rset;
tree[r][rt<<1|1].set=rset;

tree[r][rt<<1].add=0;
tree[r][rt<<1|1].add=0;

tree[r][rt].set=0;
}
if(tree[r][rt].add)
{
tree[r][rt<<1].sum+=radd*(lg-(lg>>1));
tree[r][rt<<1|1].sum+=radd*(lg>>1);

tree[r][rt<<1].mx+=radd;
tree[r][rt<<1].mn+=radd;
tree[r][rt<<1|1].mx+=radd;
tree[r][rt<<1|1].mn+=radd;

tree[r][rt<<1].add+=radd;
tree[r][rt<<1|1].add+=radd;
tree[r][rt].add=0;
}
}
void build(int r,int L,int R,int rt)
{
tree[r][rt].add=0;
tree[r][rt].set=0;
tree[r][rt].lc=L;
tree[r][rt].rc=R;
if(L==R)
{
tree[r][rt].sum=0;
tree[r][rt].mx=0;
tree[r][rt].mn=0;
return ;
}
int mid=tree[r][rt].mid();
build(r,lson);
build(r,rson);
pushup(r,rt);
}
void update_set(int r,int L,int R,int rt,int v)
{
if(L==tree[r][rt].lc&&tree[r][rt].rc==R)
{
tree[r][rt].add=0;
tree[r][rt].set=v;
tree[r][rt].sum=(R-L+1)*v;
tree[r][rt].mx=v;
tree[r][rt].mn=v;
return ;
}
pushdown(r,rt);
int mid=tree[r][rt].mid();
if(R<=mid)update_set(r,L,R,rt<<1,v);
else if(L>mid)update_set(r,L,R,rt<<1|1,v);
else
{
update_set(r,lson,v);
update_set(r,rson,v);
}
pushup(r,rt);
}
void update_add(int r,int L,int R,int rt,int v)
{
if(L==tree[r][rt].lc&&tree[r][rt].rc==R)
{
tree[r][rt].add+=v;
tree[r][rt].sum+=(R-L+1)*v;
tree[r][rt].mn+=v;
tree[r][rt].mx+=v;
return ;
}
pushdown(r,rt);
int mid=tree[r][rt].mid();
if(R<=mid)update_add(r,L,R,rt<<1,v);
else if(L>mid)update_add(r,L,R,rt<<1|1,v);
else
{
update_add(r,lson,v);
update_add(r,rson,v);
}
pushup(r,rt);
}
void query(int r,int L,int R,int rt)
{
if(L==tree[r][rt].lc&&tree[r][rt].rc==R)
{
ans+=tree[r][rt].sum;
MX=max(MX,tree[r][rt].mx);
MN=min(MN,tree[r][rt].mn);
return ;
}
pushdown(r,rt);
int mid=tree[r][rt].mid();
if(R<=mid)query(r,L,R,rt<<1);
else if(L>mid)query(r,L,R,rt<<1|1);
else
{
query(r,lson);
query(r,rson);
}
}
int main()
{
int r,c,m,k,x1,x2,y1,y2,v;
while(~scanf("%d%d%d",&r,&c,&m))
{
init(r,c);
for(int i=1;i<=r;i++)
{
build(i,1,c,1);
}
while(m--)
{
scanf("%d",&k);
if(k==1)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);
for(int i=x1;i<=x2;i++)
{
update_add(i,y1,y2,1,v);
}
}
else if(k==2)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);
for(int i=x1;i<=x2;i++)
{
update_set(i,y1,y2,1,v);
}
}
else
{
ans=0;
MX=-inf;
MN=inf;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i=x1;i<=x2;i++)
{
query(i,y1,y2,1);
}
printf("%d %d %d\n",ans,MN,MX);
}
}
deal(r,c);
}
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
#define MAXN 1000010
const int inf=0x3f3f3f3f;

stack<int>st;
int T,n;
struct data
{
int val,sz;//val满足堆,sz子树大小
int l,r,par;//左孩子,右孩子,父亲
}t[MAXN];

void init()
{
for(int i=0;i<=n;i++)
t[i].l=0,t[i].r=0,t[i].par=0,t[i].sz=0;//初始化
t[0].val=inf;
while(!st.empty()) st.pop();
st.push(0);
}

void build()
{
for(int i=1;i<=n;i++)
{
while(!st.empty()&&t[st.top()].val<t[i].val)//从栈顶往栈底遍历
st.pop();
int par=st.top();
t[i].par=par;
t[i].l=t[par].r;
t[t[par].r].par=i;
t[par].r=i;
st.push(i);
}
}

int main()
{
read(T);
while(T--)
{
read(n);
init();
for(int i=1;i<=n;i++)
read(t[i].val);
build();
}
}

树状数组

树上二分(一个log)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void change(int i,int x)
{
for(;i<=n;i+=i&(-i)) c[i]+=x;
}

int query(int i)
{
int s=0;
for (;i;i-=i&(-i)) s+=c[i];
return s;
}

int qry(int x) //i是sum[i]<x的最后一位
{
int i=0,ii,k,t=0,tt;
for (k=tot>>1;k;k>>=1)
if ((tt=t+c[ii=(i|k)])<x){t=tt;i=ii;}
return i+1;
}

区间修改,区间询问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void add(LL p,LL x)
{
for(int i=p;i<=n;i+=i&-i)
sum1[i]+=x,sum2[i]+=x*p;
}

void range_add(LL l,LL r,LL x)
{
add(l,x),add(r+1,-x);
}

LL ask(LL p)
{
LL res=0;
for(int i=p;i;i-=i&-i) res+=(p+1)*sum1[i]-sum2[i];
return res;
}

LL range_ask(LL l, LL r)
{
return ask(r)-ask(l-1);
}

三维树状数组

单点增,区间和

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
const int maxn = 128 + 10;
int N;
int c[maxn][maxn][maxn];
int lowerbit(int x){return x & (-x);}
void add(int x, int y, int z, int v)
{
for(int i = x; i <= N; i += lowerbit(i))
for(int j = y; j <= N; j += lowerbit(j))
for(int k = z; k <= N; k += lowerbit(k))
c[i][j][k] += v;
}
long long sum(int x, int y, int z)
{
long long ret = 0;
for(int i = x; i > 0; i -= lowerbit(i))
for(int j = y; j > 0; j -= lowerbit(j))
for(int k = z; k > 0; k -= lowerbit(k))
ret += c[i][j][k];
return ret;
}
int main()
{
int op;
while(scanf("%d", &N) == 1)
{
while(scanf("%d", &op) && op != 3)
{
if(op == 1)
{
int x, y, z, k;
scanf("%d%d%d%d", &x, &y, &z, &k);
add(x+1, y+1, z+1, k);
}
else
{
int x1, y1, z1, x2, y2, z2;
scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
x1++; y1++; z1++;
x2++; y2++; z2++;
printf("%I64d\n", sum(x2, y2, z2)-sum(x2, y1-1, z2)-sum(x1-1, y2, z2)+sum(x1-1, y1-1, z2)
-(sum(x2, y2, z1-1)-sum(x2, y1-1, z1-1)-sum(x1-1, y2, z1-1)+sum(x1-1, y1-1, z1-1)));
}
}
}
return 0;
}

主席树

区间k大数

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
int T,n,m,s,k,h[100010],b[100010],d[100010];
struct ST
{
int lc,rc,sum;
}a[2000010];

int Hash(int x)
{
return lower_bound(b+1,b+1+k,x)-b;
}

void build(int l,int r,int x)
{
s++;x=s;
if (l==r) {a[x].lc=a[x].rc=0;return ;}
int mid=(l+r)>>1;
a[x].lc=s+1;build(l,mid,x);
a[x].rc=s+1;build(mid+1,r,x);
}

void change(int x,int y,int z,int xx,int l,int r) //新结点编号,,,对应结点编号,[l,r]
{
if (l==r) {a[x].sum=a[xx].sum+z;return ;}
int mid=(l+r)>>1;
if (y<=mid)
{
a[x].rc=a[xx].rc;
s++;a[x].lc=s;
change(s,y,z,a[xx].lc,l,mid);
}
else
{
a[x].lc=a[xx].lc;
s++;a[x].rc=s;
change(s,y,z,a[xx].rc,mid+1,r);
}
a[x].sum=a[a[x].lc].sum+a[a[x].rc].sum;
}

int query(int x,int y,int z,int l,int r)
{
if (l==r) return b[l];
if (a[a[y].lc].sum-a[a[x].lc].sum>=z) query(a[x].lc,a[y].lc,z,l,(l+r)>>1);
else query(a[x].rc,a[y].rc,z-(a[a[y].lc].sum-a[a[x].lc].sum),((l+r)>>1)+1,r);
}

int main()
{
read(T);
while (T--)
{
read(n);read(m);
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
read(b[i]),d[i]=b[i];
sort(b+1,b+1+n);
k=unique(b+1,b+1+n)-b-1; //离散数据
s=0;
build(1,n,1);
h[0]=1;
for (int i=1;i<=n;i++)
{
s++;h[i]=s;
change(s,Hash(d[i]),1,h[i-1],1,n);
}
int x,y,z;
while(m--)
{
read(x);read(y);read(z);
print(query(h[x-1],h[y],z,1,n));putchar('\n'); //区间[x,y]中的第z大数
}
}
return 0;
}

树上k大

询问(u,v,k),回答u xor lastans和v这两个节点间第K小的点权

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
const int maxn=100010;
int n,m;
int a[maxn],b[maxn];
int pos[maxn],cnt;
struct node{int v,nxt;}E[maxn<<1];
int head[maxn],tot;
int fa[maxn],dep[maxn],top[maxn];
int size[maxn],son[maxn];
int lft[maxn<<5],rht[maxn<<5];
int rt[maxn<<5],sum[maxn<<5],sz;
int ans;

void add(int u,int v)
{
E[++tot].nxt=head[u];
E[tot].v=v;
head[u]=tot;
}

void dfs1(int u,int pa)
{
size[u]=1;
for(int i=head[u];i;i=E[i].nxt)
{
int v=E[i].v;
if(v==pa) continue;
dep[v]=dep[u]+1; fa[v]=u;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}

void dfs2(int u,int tp)
{
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=head[u];i;i=E[i].nxt)
{
int v=E[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}

int update(int pre,int ll,int rr,int x)
{
int rt=++sz;
lft[rt]=lft[pre]; rht[rt]=rht[pre]; sum[rt]=sum[pre]+1;
if(ll<rr)
{
int mid=ll+rr>>1;
if(x<=mid) lft[rt]=update(lft[pre],ll,mid,x);
else rht[rt]=update(rht[pre],mid+1,rr,x);
}
return rt;
}

void dfs(int u)
{
int x=lower_bound(pos+1,pos+1+cnt,a[u])-pos;
rt[u]=update(rt[fa[u]],1,cnt,x);//以fa[u]为上一棵主席树建树

for(int i=head[u];i;i=E[i].nxt)
if(E[i].v!=fa[u]) dfs(E[i].v);
}

int LCA(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
else v=fa[top[v]];
}
if(dep[u]<dep[v]) return u;
else return v;
}

int query(int u,int v,int lca,int gra,int ll,int rr,int k)
{
if(ll==rr) return ll;
int x=sum[lft[u]]+sum[lft[v]]-sum[lft[lca]]-sum[lft[gra]];//差分得路径
int mid=ll+rr>>1;
if(x>=k) return query(lft[u],lft[v],lft[lca],lft[gra],ll,mid,k);
else return query(rht[u],rht[v],rht[lca],rht[gra],mid+1,rr,k-x);
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;++i)
if(i==1||b[i]!=b[i-1])
pos[++cnt]=b[i];

for(int i=1;i<n;++i)
{
int u,v;scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs1(1,0); dfs2(1,1);//树剖
dfs(1);//深搜建立主席树
while(m--)
{
int u,v,k;scanf("%d%d%d",&u,&v,&k);
u^=ans;
int lca=LCA(u,v);
ans=pos[query(rt[u],rt[v],rt[lca],rt[fa[lca]],1,cnt,k)];//差分得到u到v的路径
printf("%d\n",ans);
}
return 0;
}

带修改的k大数

1 x y:把a[x]修改为y。

2 x y k:查询[x,y]内第k小值。

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
const int N = 200010, M = 524289;
int n, m, cnt, i, a[N], op[N][4], b[N];
int lower(int x)
{
int l = 1, r = cnt, t, mid;
while (l <= r)
if (b[mid = (l + r) >> 1] <= x)
l = (t = mid) + 1;
else
r = mid - 1;
return t;
}
struct node
{
int val, cnt, sum, p;
node *l, *r;
node()
{
val = sum = cnt = p = 0;
l = r = NULL;
}
inline void up() { sum = l->sum + r->sum + cnt; }
} *blank = new (node), *T[M], pool[2000000], *cur;
void Rotatel(node *&x)
{
node *y = x->r;
x->r = y->l;
x->up();
y->l = x;
y->up();
x = y;
}
void Rotater(node *&x)
{
node *y = x->l;
x->l = y->r;
x->up();
y->r = x;
y->up();
x = y;
}
void Ins(node *&x, int y, int p)
{
if (x == blank)
{
x = cur++;
x-> val = y;
x-> l = x-> r = blank;
x-> sum = x-> cnt = 1;
x-> p = std::rand();
return;
}
x-> sum += p;
if (y == x-> val)
{
x-> cnt += p;
return;
}
if (y<x-> val)
{
Ins(x-> l, y, p);
if (x-> l-> p > x-> p)
Rotater(x);
}
else
{
Ins(x-> r, y, p);
if (x-> r-> p > x-> p)
Rotatel(x);
}
}
int Ask(node *x, int y)
{ //ask how many <= y
int t = 0;
while (x != blank)
if (y<x-> val)
x = x-> l;
else
t += x-> l-> sum + x-> cnt, x = x-> r;
return t;
}
void add(int v, int i, int p)
{
int a = 1, b = cnt, mid, f = 1, x = 1;
while (a < b)
{
if (f)
Ins(T[x], i, p);
mid = (a + b) >> 1;
x <<= 1;
if (f = v <= mid)
b = mid;
else
a = mid + 1, x |= 1;
}
Ins(T[x], i, p);
}
int kth(int l, int r, int k)
{
int x = 1, a = 1, b = cnt, mid;
while (a < b)
{
mid = (a + b) >> 1;
x <<= 1;
int t = Ask(T[x], r)-Ask(T[x], l-1);
if (k <= t)
b = mid;
else
k-= t, a = mid + 1, x |= 1;
}
return a;
}
void build(int x, int a, int b)
{
T[x] = blank;
if (a == b)
return;
int mid = (a + b) >> 1;
build(x << 1, a, mid), build(x << 1 | 1, mid + 1, b);
}
int main()
{
int T;read(T);
blank-> l = blank-> r = blank;
while (T--)
{
read(n);read(m);
cur = pool;
for (i = 1; i <= n; i++)
read(a[i]), b[i] = a[i];
cnt = n;
for (i = 1; i <= m; i++)
{
read(op[i][0]), read(op[i][1]), read(op[i][2]);
if (op[i][0] == 1)
b[++cnt] = op[i][2];
else
read(op[i][3]);
}
sort(b + 1, b + cnt + 1);
for (i = 1; i <= n; i++)
a[i] = lower(a[i]);
for (i = 1; i <= m; i++)
if (op[i][0] == 1)
op[i][2] = lower(op[i][2]);
build(1, 1, cnt);
for (i = 1; i <= n; i++)
add(a[i], i, 1);
for (i = 1; i <= m; i++)
{
if (op[i][0] == 1)
add(a[op[i][1]], op[i][1],-1), add(a[op[i][1]] = op[i][2], op[i][1], 1);
else
printf("%d\n", b[kth(op[i][1], op[i][2], op[i][3])]);
}
}
}

区间不同数的个数

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
const int maxn = 30000 + 10;
int n,q,cnt = 0,la[1000000 + 10],a[maxn],root[maxn];
struct Node
{
int l,r,sum;
}p[maxn*40];

int build(int l,int r)
{
int nc = ++cnt;
p[nc].sum = 0;
p[nc].l = p[nc].r = 0;
if (l == r) return nc;
int m = l + r >> 1;
p[nc].l = build(l,m);
p[nc].r = build(m+1,r);
return nc;
}

int update(int pos,int c,int v,int l,int r)
{
int nc = ++cnt;
p[nc] = p[c];
p[nc].sum += v;
if (l == r) return nc;
int m = l+r>>1;
if (m >= pos) p[nc].l = update(pos,p[c].l,v,l,m);
else p[nc].r = update(pos,p[c].r,v,m+1,r);
return nc;
}

int query(int pos,int c,int l,int r)
{
if (l == r) return p[c].sum;
int m = l + r >> 1;
if (m >= pos) return p[p[c].r ].sum + query(pos,p[c].l,l,m);
else return query(pos,p[c].r,m+1,r);
}

int main()
{
scanf("%d",&n);
memset(la,-1,sizeof la);
for (int i = 1; i <= n; ++i)
scanf("%d",a+i);
root[0] = build(1,n);
for (int i = 1 ; i <= n; ++i)
{
int v = a[i];
if (la[v] == -1) root[i] = update(i,root[i-1],1,1,n);
else{
int t = update(la[v],root[i-1],-1,1,n);
root[i] = update(i,t,1,1,n);
}
la[v] = i;
}
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d %d",&x, &y);
printf("%d\n",query(x,root[y],1,n));
}
return 0;
}

平衡树

fhq_treap

  1. 插入x数

  2. 删除x数(若有多个相同的数,因只删除一个)

  3. 查询x数的排名(若有多个相同的数,因输出最小的排名)

  4. 查询排名为x的数

  5. 求x的前驱(前驱定义为小于x,且最大的数)

  6. 求x的后继(后继定义为大于x,且最小的数)

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
const int maxn=1e5+5;
struct node
{
int son[2],v,rnd,size;
}tr[maxn];
int n,m,l,r;
int tot,root;
int new_node(int v)//创建权值为v的结点。
{
tot++;
tr[tot].size=1;
tr[tot].v=v;
tr[tot].rnd=rand();
tr[tot].son[0]=tr[tot].son[1]=0;
return tot;
}
void update(int x)
{
tr[x].size=tr[tr[x].son[0]].size+tr[tr[x].son[1]].size+1;
}
int merge(int x,int y)
{
if(!x||!y)
return x+y;
if(tr[x].rnd<tr[y].rnd)
{
tr[x].son[1]=merge(tr[x].son[1],y);
update(x);
return x;
}
else
{
tr[y].son[0]=merge(x,tr[y].son[0]);
update(y);
return y;
}
}
void split(int now,int k,int &x,int &y)//以权值k分离now树成x,y
{
if(!now) x=y=0;
else
{
if(tr[now].v<=k) //把所有小于等于k的权值的节点分到一棵树中
x=now,split(tr[now].son[1],k,tr[now].son[1],y);
else
y=now,split(tr[now].son[0],k,x,tr[now].son[0]);
update(now);
}
}
void rev(int l,int r)
{
int x,y,u,v;
split(root,r+1,x,y);
split(x,l,u,v);
root=merge(merge(u,v),y);
}
void insert(int v)
{
int x,y;
split(root,v,x,y);
root=merge(merge(x,new_node(v)),y);
}
void del(int v)
{
int x,y,z;
split(root,v,x,z);
split(x,v-1,x,y);
y=merge(tr[y].son[0],tr[y].son[1]);
root=merge(merge(x,y),z);
}
void findrank(int v)
{
int x,y;
split(root,v-1,x,y);
printf("%d\n",tr[x].size+1);
root=merge(x,y);
}
int kth(int now,int k)
{
while(1)
{
if(k<=tr[tr[now].son[0]].size)
now=tr[now].son[0];
else
{
if(k==tr[tr[now].son[0]].size+1) return now;
else
{
k-=tr[tr[now].son[0]].size+1;
now=tr[now].son[1];
}
}
}
}
void precursor(int v)
{
int x,y;
split(root,v-1,x,y);
printf("%d\n",tr[kth(x,tr[x].size)].v);
root=merge(x,y);
}
void successor(int v)
{
int x,y;
split(root,v,x,y);
printf("%d\n",tr[kth(y,1)].v);
root=merge(x,y);
}
int main()
{
srand((unsigned)time(NULL));
int n,op,v;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&op,&v);
switch(op)
{
case 1:insert(v);break;
case 2:del(v);break;
case 3:findrank(v);break;
case 4:printf("%d\n",tr[kth(root,v)].v);break;
case 5:precursor(v);break;
case 6:successor(v);break;
default:break;
}
}
return 0;
}

可持久化treap

1.插入x数

2.删除x数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)

3.查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)

4.查询排名为x的数

5.求x的前驱(前驱定义为小于x,且最大的数,如不存在输出-2147483647)

6.求x的后继(后继定义为大于x,且最小的数,如不存在输出2147483647)

第 i 行记为 vi,opti,xiv_i,opt_i,x_ivi​,opti​,xi​,viv_ivi​表示基于的过去版本号

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
#define SF scanf
#define PF printf
#define MAXN 500010
using namespace std;
struct node{
int ch[2];
int key,sum,fix;
node () {}
node (int key1):key(key1),fix(rand()),sum(1) {}
}Tree[MAXN*30];
int ncnt,root[MAXN];
void update(int x){
Tree[x].sum=Tree[Tree[x].ch[0]].sum+Tree[Tree[x].ch[1]].sum+1;
}
int Merge(int x,int y){
if(x==0) return y;
if(y==0) return x;
if(Tree[x].fix<Tree[y].fix){
Tree[x].ch[1]=Merge(Tree[x].ch[1],y);
update(x);
return x;
}
else{
Tree[y].ch[0]=Merge(x,Tree[y].ch[0]);
update(y);
return y;
}
}
pair<int,int> Split(int x,int k){
if(x==0)
return make_pair(0,0);
int newone;
pair<int,int> y;
if(Tree[x].key<=k){
newone=++ncnt;
Tree[newone]=Tree[x];
y=Split(Tree[newone].ch[1],k);
Tree[newone].ch[1]=y.first;
update(newone);
y.first=newone;
}
else{
newone=++ncnt;
Tree[newone]=Tree[x];
y=Split(Tree[newone].ch[0],k);
Tree[newone].ch[0]=y.second;
update(newone);
y.second=newone;
}
return y;
}
int find_kth(int now,int val){
pair<int,int> x=Split(root[now],val-1);
int ans=Tree[x.first].sum+1;
root[now]=Merge(x.first,x.second);
return ans;
}
int get_kth(int x,int k){
if(x==0)
return 0;
int ch0=Tree[x].ch[0];
if(Tree[ch0].sum>=k)
return get_kth(ch0,k);
if(Tree[ch0].sum+1==k)
return Tree[x].key;
return get_kth(Tree[x].ch[1],k-Tree[ch0].sum-1);
}
int get_pre(int now,int val){
int k=find_kth(now,val);
return get_kth(root[now],k-1);
}
int get_bac(int now,int val){
pair<int,int> x=Split(root[now],val);
int ans=get_kth(x.second,1);
root[now]=Merge(x.first,x.second);
return ans;
}
void Insert(int val,int now){
pair<int,int> x=Split(root[now],val);
Tree[++ncnt]=node(val);
Tree[ncnt].ch[0]=0;
Tree[ncnt].ch[1]=0;
root[now]=Merge(Merge(x.first,ncnt),x.second);
}
void Delete(int val,int now){
pair<int,int> x=Split(root[now],val);
pair<int,int> y=Split(x.first,val-1);
if(Tree[y.second].key==val)
y.second=Merge(Tree[y.second].ch[0],Tree[y.second].ch[1]);
root[now]=Merge(Merge(y.first,y.second),x.second);
}
int n,las,x,tag;
int main(){
SF("%d",&n);
Insert(-2147483647,0);
Insert(2147483647,0);
for(int i=1;i<=n;i++){
SF("%d%d%d",&las,&tag,&x);
if(Tree[root[las]].sum!=0){
root[i]=++ncnt;
Tree[root[i]]=Tree[root[las]];
}
if(tag==1)
Insert(x,i);
if(tag==2)
Delete(x,i);
if(tag==3)
PF("%d\n",find_kth(i,x)-1);
if(tag==4)
PF("%d\n",get_kth(root[i],x+1));
if(tag==5)
PF("%d\n",get_pre(i,x));
if(tag==6)
PF("%d\n",get_bac(i,x));
}
}

Segment Beats

维护一个序列,支持下面几种操作:

1.给一个区间[L, R]加上一个数x。

2.把一个区间[L, R]里小于x的数变成x。

3.把一个区间[L, R]里大于x的数变成x。

4.求区间[L, R]的和。

5.求区间[L, R]的最大值。

6.求区间[L, R]的最小值。

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
const int N = 1050000, inf = ~0U >> 1;
int n, m, i, a[500010], op, c, d, p, ans;
int len[N], cma[N], cmi[N], ma[N], ma2[N], mi[N], mi2[N], tma[N], tmi[N], ta[N];
long long sum[N], ret;
void tagma(int x, int p)
{
tma[x] += p;
if (ma[x] == mi[x])
{
ma[x] += p;
mi[x] = ma[x];
sum[x] = 1LL * ma[x] * len[x];
return;
}
ma[x] += p;
if (cma[x] + cmi[x] == len[x])
mi2[x] += p;
sum[x] += 1LL * p * cma[x];
}
void tagmi(int x, int p)
{
tmi[x] += p;
if (ma[x] == mi[x])
{
ma[x] += p;
mi[x] = ma[x];
sum[x] = 1LL * ma[x] * len[x];
return;
}
mi[x] += p;
if (cma[x] + cmi[x] == len[x])
ma2[x] += p;
sum[x] += 1LL * p * cmi[x];
}
void taga(int x, int p)
{
ta[x] += p;
ma[x] += p;
mi[x] += p;
if (ma2[x] !=-inf)
ma2[x] += p;
if (mi2[x] != inf)
mi2[x] += p;
sum[x] += 1LL * p * len[x];
}
void pb(int x)
{
if (tma[x])
{
if (ma[x << 1] > ma[x << 1 | 1])
tagma(x << 1, tma[x]);
else if (ma[x << 1] < ma[x << 1 | 1])
tagma(x << 1 | 1, tma[x]);
else
{
tagma(x << 1, tma[x]);
tagma(x << 1 | 1, tma[x]);
}
tma[x] = 0;
}
if (tmi[x])
{
if (mi[x << 1] < mi[x << 1 | 1])
tagmi(x << 1, tmi[x]);
else if (mi[x << 1] > mi[x << 1 | 1])
tagmi(x << 1 | 1, tmi[x]);
else
{
tagmi(x << 1, tmi[x]);
tagmi(x << 1 | 1, tmi[x]);
}
tmi[x] = 0;
}
if (ta[x])
{
taga(x << 1, ta[x]);
taga(x << 1 | 1, ta[x]);
ta[x] = 0;
}
}
void up(int x)
{
sum[x] = sum[x << 1] + sum[x << 1 | 1];
if (ma[x << 1] > ma[x << 1 | 1])
{
ma[x] = ma[x << 1];
ma2[x] = max(ma2[x << 1], ma[x << 1 | 1]);
cma[x] = cma[x << 1];
}
else if (ma[x << 1] < ma[x << 1 | 1])
{
ma[x] = ma[x << 1 | 1];
ma2[x] = max(ma[x << 1], ma2[x << 1 | 1]);
cma[x] = cma[x << 1 | 1];
}
else
{
ma[x] = ma[x << 1];
ma2[x] = max(ma2[x << 1], ma2[x << 1 | 1]);
cma[x] = cma[x << 1] + cma[x << 1 | 1];
}
if (mi[x << 1] < mi[x << 1 | 1])
{
mi[x] = mi[x << 1];
mi2[x] = min(mi2[x << 1], mi[x << 1 | 1]);
cmi[x] = cmi[x << 1];
}
else if (mi[x << 1] > mi[x << 1 | 1])
{
mi[x] = mi[x << 1 | 1];
mi2[x] = min(mi[x << 1], mi2[x << 1 | 1]);
cmi[x] = cmi[x << 1 | 1];
}
else
{
mi[x] = mi[x << 1];
mi2[x] = min(mi2[x << 1], mi2[x << 1 | 1]);
cmi[x] = cmi[x << 1] + cmi[x << 1 | 1];
}
}
void build(int x, int a, int b)
{
len[x] = b-a + 1;
if (a == b)
{
ma[x] = mi[x] = sum[x] = ::a[a], ma2[x] =-inf, mi2[x] = inf;
cma[x] = cmi[x] = 1;
return;
}
int mid = (a + b) >> 1;
build(x << 1, a, mid), build(x << 1 | 1, mid + 1, b);
up(x);
}
void change(int x, int a, int b)
{
if (c <= a && b <= d)
{
taga(x, p);
return;
}
pb(x);
int mid = (a + b) >> 1;
if (c <= mid)
change(x << 1, a, mid);
if (d > mid)
change(x << 1 | 1, mid + 1, b);
up(x);
}
void cmax(int x, int a, int b)
{
if (c <= a && b <= d)
{
if (mi[x] >= p)
return;
if (mi2[x] > p)
{
tagmi(x, p-mi[x]);
return;
}
}
pb(x);
int mid = (a + b) >> 1;
if (c <= mid)
cmax(x << 1, a, mid);
if (d > mid)
cmax(x << 1 | 1, mid + 1, b);
up(x);
}
void cmin(int x, int a, int b)
{
if (c <= a && b <= d)
{
if (ma[x] <= p)
return;
if (ma2[x] < p)
{
tagma(x, p-ma[x]);
return;
}
}
pb(x);
int mid = (a + b) >> 1;
if (c <= mid)
cmin(x << 1, a, mid);
if (d > mid)
cmin(x << 1 | 1, mid + 1, b);
up(x);
}
void qsum(int x, int a, int b)
{
if (c <= a && b <= d)
{
ret += sum[x];
return;
}
pb(x);
int mid = (a + b) >> 1;
if (c <= mid)
qsum(x << 1, a, mid);
if (d > mid)
qsum(x << 1 | 1, mid + 1, b);
}
void qmax(int x, int a, int b)
{
if (c <= a && b <= d)
{
ans = max(ans, ma[x]);
return;
}
pb(x);
int mid = (a + b) >> 1;
if (c <= mid)
qmax(x << 1, a, mid);
if (d > mid)
qmax(x << 1 | 1, mid + 1, b);
}
void qmin(int x, int a, int b)
{
if (c <= a && b <= d)
{
ans = min(ans, mi[x]);
return;
}
pb(x);
int mid = (a + b) >> 1;
if (c <= mid)
qmin(x << 1, a, mid);
if (d > mid)
qmin(x << 1 | 1, mid + 1, b);
}
int main()
{
for (read(n), i = 1; i <= n; i++)
read(a[i]);
build(1, 1, n);
read(m);
while (m--)
{
read(op), read(c), read(d);
if (op == 1)
read(p), change(1, 1, n);
if (op == 2)
read(p), cmax(1, 1, n);
if (op == 3)
read(p), cmin(1, 1, n);
if (op == 4)
ret = 0, qsum(1, 1, n), printf("% lld\n", ret);
if (op == 5)
ans =-inf, qmax(1, 1, n), printf("% d\n", ans);
if (op == 6)
ans = inf, qmin(1, 1, n), printf("% d\n", ans);
}
}

动态树

树的连通性

Connect u v:链接uv;

Destroy u v:断开uv;

Query u v:询问uv是否联通。

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
int n,m;
struct data
{
int fa,lc,rc,rev,pfa;
}a[10010];

void Pushdown(int x)
{
if (a[x].rev)
{
a[x].rev=0;
a[a[x].lc].rev^=1;
a[a[x].rc].rev^=1;
swap(a[x].lc,a[x].rc);
}
}

void Pushpath(int x)
{
if (a[x].fa!=0) Pushpath(a[x].fa);
Pushdown(x);
}

void zag(int x)
{
int y=a[x].fa;
a[x].pfa=a[y].pfa;a[y].pfa=0;
a[y].rc=a[x].lc;
if (a[x].lc!=0) a[a[x].lc].fa=y;
a[x].fa=a[y].fa;
if (a[y].fa!=0)
{
if (y==a[a[y].fa].lc) a[a[y].fa].lc=x;
else a[a[y].fa].rc=x;
}
a[y].fa=x;a[x].lc=y;
}

void zig(int x)
{
int y=a[x].fa;
a[x].pfa=a[y].pfa;a[y].pfa=0;
a[y].lc=a[x].rc;
if (a[x].rc!=0) a[a[x].rc].fa=y;
a[x].fa=a[y].fa;
if (a[y].fa!=0)
{
if (y==a[a[y].fa].lc) a[a[y].fa].lc=x;
else a[a[y].fa].rc=x;
}
a[y].fa=x;a[x].rc=y;
}

void spaly(int x)
{
int y,z;
Pushpath(x);
while (a[x].fa!=0)
{
y=a[x].fa;
if (a[y].fa==0)
{
if (x==a[y].lc) zig(x);else zag(x);
}
else if (a[y].lc==x)
{
z=a[y].fa;
if (y==a[z].lc) zig(y),zig(x);else zig(x),zag(x);
}
else
{
z=a[y].fa;
if (y==a[z].lc) zag(x),zig(x);else zag(y),zag(x);
}
}
}

void Access(int x)
{
spaly(x);Pushdown(x);
int y=a[x].rc;
a[x].rc=a[y].fa=0;
a[y].pfa=x;y=a[x].pfa;
while (y!=0)
{
spaly(y);
Pushdown(y);
a[a[y].rc].fa=0;
a[a[y].rc].pfa=y;
a[y].rc=x;
a[x].fa=y;a[x].pfa=0;
x=y;
y=a[x].pfa;
}
spaly(x);
}

void Makeroot(int x)
{
Access(x);
spaly(x);
a[x].rev^=1;
Pushdown(x);
}

int Findroot(int x)
{
Access(x);
spaly(x);
Pushdown(x);
while (a[x].lc!=0) x=a[x].lc,Pushdown(x);
spaly(x);
return x;
}

void Join(int x,int y)
{
Makeroot(x);
spaly(x);
Pushdown(x);
Access(y);
spaly(y);
Pushdown(y);
a[x].lc=y;a[y].fa=x;
}

void Cut(int x,int y)
{
Makeroot(x);
Access(y);
spaly(y);
Pushdown(y);
a[a[y].lc].fa=0;
a[y].lc=0;
}

int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n);read(m);
for (int i=1;i<=n;i++)
a[i].fa=a[i].lc=a[i].rc=a[i].rev=a[i].pfa=0;
int x,y;char order[20];
while (m--)
{
x=read(order);
read(x);read(y);
if (order[0]=='Q')
{
if (Findroot(x)==Findroot(y)) puts("Yes");
else puts("No");
}
else if (order[0]=='C') Join(x,y);
else if (order[0]=='D') Cut(x,y);
}
return 0;
}

链和与最大最小

CHANGE u t : 把结点u的权值改为t

QMAX u v: 询问从点u到点v的路径上的节点的最大权值

QSUM u v: 询问从点u到点v的路径上的节点的权值和

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
int n,m;
struct data
{
int fa,lc,rc,rev,pfa;
LL xsum,lsum,rsum,lmax,rmax,xmax;
}a[300010];

void Pushdown(int x)
{
if (a[x].rev)
{
a[x].rev=0;
a[a[x].lc].rev^=1;
a[a[x].rc].rev^=1;
swap(a[x].lc,a[x].rc);
swap(a[x].lsum,a[x].rsum);
swap(a[x].lmax,a[x].rmax);
}
}

void Pushpath(int x)
{
if (a[x].fa!=0) Pushpath(a[x].fa);
Pushdown(x);
}

void zag(int x)
{
int y=a[x].fa;
a[x].pfa=a[y].pfa;a[y].pfa=0;
a[y].rc=a[x].lc;
if (a[x].lc!=0) a[a[x].lc].fa=y;
a[x].fa=a[y].fa;
if (a[y].fa!=0)
{
if (y==a[a[y].fa].lc) a[a[y].fa].lc=x;
else a[a[y].fa].rc=x;
}
a[y].fa=x;a[x].lc=y;
int t=a[x].lsum;a[x].lsum+=a[y].xsum+a[y].lsum;a[y].rsum=t;
LL q=a[x].lmax;a[x].lmax=max(max(a[x].lmax,a[y].xmax),a[y].lmax);a[y].rmax=q;
}

void zig(int x)
{
int y=a[x].fa;
a[x].pfa=a[y].pfa;a[y].pfa=0;
a[y].lc=a[x].rc;
if (a[x].rc!=0) a[a[x].rc].fa=y;
a[x].fa=a[y].fa;
if (a[y].fa!=0)
{
if (y==a[a[y].fa].lc) a[a[y].fa].lc=x;
else a[a[y].fa].rc=x;
}
a[y].fa=x;a[x].rc=y;
int t=a[x].rsum;a[x].rsum+=a[y].xsum+a[y].rsum;a[y].lsum=t;
LL q=a[x].rmax;a[x].rmax=max(max(a[x].rmax,a[y].xmax),a[y].rmax);a[y].lmax=q;
}

void spaly(int x)
{
int y,z;
Pushpath(x);
while (a[x].fa!=0)
{
y=a[x].fa;
if (a[y].fa==0)
{
if (x==a[y].lc) zig(x);else zag(x);
}
else if (a[y].lc==x)
{
z=a[y].fa;
if (y==a[z].lc) zig(y),zig(x);else zig(x),zag(x);
}
else
{
z=a[y].fa;
if (y==a[z].lc) zag(x),zig(x);else zag(y),zag(x);
}
}
}

void Access(int x)
{
spaly(x);Pushdown(x);
int y=a[x].rc;
a[x].rc=a[y].fa=0;
a[x].rsum=0;a[x].rmax=-30010LL*200010LL;
a[y].pfa=x;y=a[x].pfa;
while (y!=0)
{
spaly(y);
Pushdown(y);
a[a[y].rc].fa=0;
a[a[y].rc].pfa=y;
a[y].rc=x;
a[y].rsum=a[x].lsum+a[x].rsum+a[x].xsum;
a[y].rmax=max(max(a[x].lmax,a[x].rmax),a[x].xmax);
a[x].fa=y;a[x].pfa=0;
x=y;
y=a[x].pfa;
}
spaly(x);
}

void Makeroot(int x)
{
Access(x);
spaly(x);
a[x].rev^=1;
Pushdown(x);
}

int Findroot(int x)
{
Access(x);
spaly(x);
Pushdown(x);
while (a[x].lc!=0) x=a[x].lc,Pushdown(x);
spaly(x);
return x;
}

void Join(int x,int y)
{
Makeroot(x);
spaly(x);
Pushdown(x);
Access(y);
spaly(y);
Pushdown(y);
a[x].lc=y;a[y].fa=x;
a[x].lsum=a[y].xsum+a[y].lsum+a[y].rsum;
a[x].lmax=max(max(a[y].xmax,a[y].lmax),a[y].rmax);
}

void Cut(int x,int y)
{
Makeroot(x);
Access(y);
spaly(y);
Pushdown(y);
a[a[y].lc].fa=0;
a[y].lc=0;
a[y].lsum=0;a[y].lmax=-30010LL*200010LL;
}

void Updata(int x,int y)
{
spaly(x);
Pushdown(x);
a[x].xmax=y;a[x].xsum=y;
}

LL querymax(int x,int y)
{
Makeroot(x);
Access(y);
spaly(y);
Pushdown(y);
return max(a[y].lmax,a[y].xmax);
}

LL querysum(int x,int y)
{
Makeroot(x);
Access(y);
spaly(y);
Pushdown(y);
return a[y].lsum+a[y].xsum;
}

int main()
{
freopen("bzoj_1036.in","r",stdin);
freopen("bzoj_1036.out","w",stdout);
read(n);
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
a[i].lmax=-30010LL*200010LL,a[i].rmax=-30010LL*200010LL,a[i].xmax=-30010LL*200010LL;
int x,y;LL z;char o[100];
for (int i=1;i<n;i++)
read(x),read(y),Join(x,y);
for (int i=1;i<=n;i++)
read(z),Updata(i,z);
read(m);
while (m--)
{
x=read(o);
if (o[1]=='M') read(x),read(y),print(querymax(x,y)),puts("");
else if (o[1]=='S') read(x),read(y),print(querysum(x,y)),puts("");
else read(x),read(z),Updata(x,z);
}
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
int n,m,point[100010],po,T;
struct data
{
int fa,top,c,ne,d,point,l,r;
LL x;
}a[100010];
vector<int> b[100010];
bool v[100010];
struct ST
{
LL x,tag;
}tree[400010];

void dfs1(int x)
{
v[x]=true;
int Max=0,w=0;
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i]])
{
a[b[x][i]].d=a[x].d+1;
dfs1(b[x][i]);
if (a[b[x][i]].c>Max) Max=a[b[x][i]].c,w=b[x][i];
a[x].c+=a[b[x][i]].c;
a[b[x][i]].fa=x;
}
a[x].ne=w;a[x].c++;
}

void dfs2(int x,int y)
{
v[x]=true,point[++po]=x,a[x].point=po,a[x].top=y;a[x].l=po;
if (!v[a[x].ne] && a[x].ne!=0) dfs2(a[x].ne,a[x].top);
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i]])
dfs2(b[x][i],b[x][i]);
a[x].r=po;
}

void Pushdown(int x,int l,int r)
{
if (tree[x].tag!=0)
{
tree[x<<1].tag+=tree[x].tag;
tree[x<<1|1].tag+=tree[x].tag;
tree[x].x+=tree[x].tag*(LL)(r-l+1);
tree[x].tag=0;
}
}

void change(int lq,int rq,int x,int l,int r,LL z)
{
if (lq<=l && rq>=r) {tree[x].tag+=z;return ;}
int mid=l+r>>1;
Pushdown(x,l,r);
if (lq<=mid) change(lq,rq,x<<1,l,mid,z);
if (rq>mid) change(lq,rq,x<<1|1,mid+1,r,z);
tree[x].x=tree[x<<1].x+tree[x<<1|1].x+tree[x<<1].tag*(LL)(mid-l+1)+tree[x<<1|1].tag*(LL)(r-mid);
}

LL query(int lq,int rq,int x,int l,int r)
{
if (lq<=l && rq>=r) return tree[x].x+tree[x].tag*(LL)(r-l+1);
int mid=l+r>>1;
LL res=0;
Pushdown(x,l,r);
if (lq<=mid) res+=query(lq,rq,x<<1,l,mid);
if (rq>mid) res+=query(lq,rq,x<<1|1,mid+1,r);
tree[x].x=tree[x<<1].x+tree[x<<1|1].x+tree[x<<1].tag*(LL)(mid-l+1)+tree[x<<1|1].tag*(LL)(r-mid);
return res;
}

void build(int l,int r,int x)
{
if (l==r) {tree[x].x=a[point[l]].x;return ;}
int mid=l+r>>1;
build(l,mid,x<<1);build(mid+1,r,x<<1|1);
tree[x].x=tree[x<<1].x+tree[x<<1|1].x;
tree[x].tag=0;
}

int main()
{
read(n);read(m);
int x,y;LL z;
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
read(a[i].x);
for (int i=1;i<n;i++)
read(x),read(y),b[x].push_back(y),b[y].push_back(x);
memset(tree,0,sizeof(tree));
memset(v,false,sizeof(v));
a[1].d=1;a[1].fa=1;
dfs1(1);
memset(v,false,sizeof(v));
x=1;int s=0;po=0;
dfs2(1,1);
build(1,n,1);
while(m--)
{
read(x);
if (x==1) read(x),read(z),change(a[x].point,a[x].point,1,1,n,z);
else if (x==2) read(x),read(z),change(a[x].l,a[x].r,1,1,n,z);
else if (x==3)
{
read(x);LL res=0;
while (a[x].top!=1)
{
res+=query(a[a[x].top].point,a[x].point,1,1,n);
x=a[a[x].top].fa;
}
res+=query(a[1].point,a[x].point,1,1,n);
print(res);putchar('\n');
}
}
return 0;
}

LCA

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
int n,m,point[50010],po,T,way[50010],bu[50010];
struct data
{
int fa,top,c,ne,d,point,l,r;
LL x;
LL b[250];
}a[50010];
struct dara
{
int x;LL y;
dara(int a,LL b):x(a),y(b){};
};
vector<dara> b[50010];
bool v[50010];

void dfs1(int x)
{
v[x]=true;
int Max=0,w=0;
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i].x])
{
a[b[x][i].x].d=a[x].d+1;
a[b[x][i].x].x=b[x][i].y;
dfs1(b[x][i].x);
if (a[b[x][i].x].c>Max) Max=a[b[x][i].x].c,w=b[x][i].x;
a[x].c+=a[b[x][i].x].c;
a[b[x][i].x].fa=x;
}
a[x].ne=w;a[x].c++;
}

void dfs2(int x,int y)
{
v[x]=true,point[++po]=x,a[x].point=po,a[x].top=y;a[x].l=po;
if (!v[a[x].ne] && a[x].ne!=0) dfs2(a[x].ne,a[x].top);
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i].x])
dfs2(b[x][i].x,b[x][i].x);
a[x].r=po;
}

void calc(int x,int y)
{
int z=x;v[x]=true;
for (int i=1;i<=y;i++)
{
z=a[z].fa;
a[x].b[i]=a[z].b[i]+a[x].x;
}
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i].x]) calc(b[x][i].x,y);
}

int Find(int x,int y) //找x向上y个
{
while (a[x].d-a[a[x].top].d<y) y-=a[x].d-a[a[x].top].d+1,x=a[a[x].top].fa;
return point[a[x].point-y];
}

int lca(int x,int y) //点x、y的lca
{
while (a[x].top!=a[y].top)
{
if (a[a[x].top].d<a[a[y].top].d) swap(x,y);
x=a[a[x].top].fa;
}
if (a[x].d>a[y].d) swap(x,y);
return x;
}

int dist(int x,int y) //点x、y距离
{
int z=lca(x,y);
return a[x].d+a[y].d-2*a[z].d;
}

int Ans(int x,int y)
{
LL b[50010];
int s=0;
while (x!=y)
{
if (a[x].d<a[y].d) swap(x,y);
b[++s]=a[x].x;
x=a[x].fa;
}
sort(b+1,b+1+s);
return b[(s+1)/2];
}

int main()
{
freopen("draw.in","r",stdin);
freopen("draw.out","w",stdout);
read(n);
int x,y;LL z;
memset(a,0,sizeof(a));
for (int i=1;i<n;i++)
read(x),read(y),read(z),b[x].push_back(dara(y,z)),b[y].push_back(dara(x,z));
memset(v,false,sizeof(v));
a[1].d=1;a[1].fa=1;
dfs1(1);
memset(v,false,sizeof(v));
x=1;int s=0;po=0;
dfs2(1,1);
LL ans=0;
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
if (dist(i,j)%2==1) ans+=Ans(i,j);
print(ans);puts("");
return 0;
}

可并堆

Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人,那么就忽略该命令。

Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了,这条命令就忽略。 皇帝希望他每发布一条kill命令,下面的将军就把被杀的人的分数报上来。

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
int n,m,fa[1000010];
bool v[1000010];
struct data
{
int key,dist,l,r;
}tree[1000010];

int merge(int x,int y)
{
if (x==0 || y==0) return x+y;
if (tree[x].key>tree[y].key) swap(x,y);
tree[x].r=merge(tree[x].r,y);
if (tree[tree[x].r].dist>tree[tree[x].l].dist) swap(tree[x].l,tree[x].r);
if (tree[x].r==0) tree[x].dist=0;
else tree[x].dist=tree[tree[x].r].dist+1;
return x;
}

int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}

int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&tree[i].key),fa[i]=i;
scanf("%d",&m);
char x[10];int y,z;
memset(v,false,sizeof(v));
while (m--)
{
scanf("%s",x);
if (x[0]=='M')
{
scanf("%d%d",&y,&z);
if (v[y] || v[z]) continue;
y=find(y);z=find(z);
if (y==z) continue;
fa[z]=fa[y]=merge(y,z);
}
else
{
scanf("%d",&y);z=find(y);
if (v[y]) {printf("0\n");continue;}else v[z]=true;
printf("%d\n",tree[z].key);
int p=merge(tree[fa[y]].l,tree[fa[y]].r);
fa[fa[y]]=p;fa[p]=p;
}
}
return 0;
}

CDQ

三维偏序(计数)

满足i<ji<ji<j且ai<aja_i<a_jai​<aj​且bi<bjb_i<b_jbi​<bj​且ci<cjc_i<c_jci​<cj​的数对(i,j)(i,j)(i,j)的个数

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
typedef long long ll;
const int N=5e4+10;
struct Node { int b,c,d,e; } a[N], t1[N], t2[N];
ll ans;

int C[N];
#define lowbit(x) x&-x
void updata(int x, int d) {
while(x<N) {
C[x]+=d;
x+=lowbit(x);
}
}
int query(int x) {
int ret=0;
while(x) {
ret+=C[x];
x-=lowbit(x);
}
return ret;
}

void merge2(int l, int r) {
if(l==r) return;
int mid=(l+r)>>1;
merge2(l, mid), merge2(mid+1, r);
int i=l, j=mid+1, k=l;
Node *a=t1, *t=t2;
while(i<=mid && j<=r) {
if(a[i].c<a[j].c) {
if(!a[i].e) updata(a[i].d, 1);
t[k++]=a[i++];
}
else {
if(a[j].e) ans+=query(a[j].d);
t[k++]=a[j++];
}
}
while(j<=r) {
if(a[j].e) ans+=query(a[j].d);
t[k++]=a[j++];
}
for(int ni=l;ni<i;ni++) if(!a[ni].e) updata(a[ni].d, -1);
while(i<=mid) t[k++]=a[i++];
for(int i=l;i<=r;i++) a[i]=t[i];
}

void merge(int l, int r) {
if(l==r) return;
int mid=(l+r)>>1;
merge(l, mid), merge(mid+1, r);
Node *t=t1;
int i=l, j=mid+1, k=l;
while(i<=mid && j<=r) {
if(a[i].b<a[j].b) a[i].e=0, t[k++]=a[i++];
else a[j].e=1, t[k++]=a[j++];
}
while(i<=mid) a[i].e=0, t[k++]=a[i++];
while(j<=r) a[j].e=1, t[k++]=a[j++];
for(int i=l;i<=r;i++) a[i]=t[i];
merge2(l, r);
}

template<typename T> void gn(T &x) {
x=0;
char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
int n;
gn(n);
for(int i=1;i<=n;i++) gn(a[i].b);
for(int i=1;i<=n;i++) gn(a[i].c);
for(int i=1;i<=n;i++) gn(a[i].d);
merge(1, n);
printf("%lld\n", ans);
return 0;
}

四维偏序(计数)

满足i<ji<ji<j且ai<aja_i<a_jai​<aj​且bi<bjb_i<b_jbi​<bj​且ci<cjc_i<c_jci​<cj​且di<djd_i<d_jdi​<dj​的数对(i,j)(i,j)(i,j)的个数

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
#define Inf 2e9
#define Lowbit(x) (x&-x)
const int maxn=55000;
struct Node{
int id,x,y,z,q,flag1,flag2;
}a[maxn],b[maxn],c[maxn],d[maxn];
int ans=0,C[maxn],tim[maxn],Tim,n;
int Query(int x){
int res=0;
for(int i=x;i;i-=Lowbit(i)){
if(tim[i]!=Tim){tim[i]=Tim;C[i]=0;}
res+=C[i];
}
return res;
}
void Update(int x){
for(int i=x;i<=n;i+=Lowbit(i)){
if(tim[i]!=Tim){tim[i]=Tim;C[i]=0;}
C[i]++;
}
}
void CDQ3(int l,int r){
if(l>=r)return;
int mid=(l+r)>>1;
CDQ3(l,mid);CDQ3(mid+1,r);
Tim++;
int i=l,j=mid+1,k=l;
while(i<=mid && j<=r){
if(c[i].z<c[j].z){
if(c[i].flag1 && c[i].flag2)Update(c[i].q);
d[k++]=c[i++];
}
else {
if(!c[j].flag1 && !c[j].flag2)ans+=Query(c[j].q);
d[k++]=c[j++];
}
}
while(i<=mid){
if(c[i].flag1 && c[i].flag2)Update(c[i].q);
d[k++]=c[i++];
}
while(j<=r){
if(!c[j].flag1 && !c[j].flag2)ans+=Query(c[j].q);
d[k++]=c[j++];
}
for(i=l;i<=r;i++)c[i]=d[i];
}
void CDQ2(int l,int r){
if(l>=r)return;
int mid=(l+r)>>1;
CDQ2(l,mid);CDQ2(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid && j<=r){
if(b[i].y<b[j].y){
c[k].flag2=b[i].flag2=true;c[k++]=b[i++];
}
else {
c[k].flag2=b[j].flag2=false;c[k++]=b[j++];
}
}
while(i<=mid){
c[k].flag2=b[i].flag2=true;c[k++]=b[i++];
}
while(j<=r){
c[k].flag2=b[j].flag2=false;c[k++]=b[j++];
}
for(i=l;i<=r;i++)b[i]=c[i];
CDQ3(l,r);
}
void CDQ1(int l,int r){
if(l>=r)return;
int mid=(l+r)>>1;
CDQ1(l,mid);CDQ1(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid && j<=r){
if(a[i].x<a[j].x)b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
for(i=l;i<=r;i++){
a[i]=b[i];
if(a[i].id<=mid)a[i].flag1=b[i].flag1=true;
else a[i].flag1=b[i].flag1=false;
}
CDQ2(l,r);
}
void Init();
int main(){
freopen("partial_order_two.in","r",stdin);freopen("partial_order_two.out","w",stdout);
Init();
return 0;
}
void Init(){
scanf("%d",&n);
for(int i=1;i<=n;i++)a[i].id=i,scanf("%d",&a[i].x);
for(int i=1;i<=n;i++)scanf("%d",&a[i].y);
for(int i=1;i<=n;i++)scanf("%d",&a[i].z);
for(int i=1;i<=n;i++)scanf("%d",&a[i].q);
CDQ1(1,n);
printf("%d\n",ans);
}

k维偏序(计数)

求i<j,1<=t<=k,pit<pjti<j,1<=t<=k,pt_i<pt_ji<j,1<=t<=k,pit​<pjt​的数量。

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
typedef bitset<40001>bit;

const int N=40005;
int n,k,siz,block[N];

struct Bitset{
int a[N],lis[N];
//lis[N]表示权值为n的点的编号
bit B[201];
//bit内储存第i维权值小于j*j的向量
bit get(int p){
p=a[p]; int bp=block[p]; bit ans=B[bp-1];
for(int i=(bp-1)*siz+1;i<p;i++) ans.set(lis[i]);
return ans;
}
}d[7];

void build(int op){
for(int i=1;i<=n;i++) d[op].lis[d[op].a[i]]=i;
bit t; t.reset();
for(int i=1;i<=n;i++){
t.set(d[op].lis[i]);
if(i%siz==0) d[op].B[i/siz]=t;
}
}

int main(){
freopen("partial_order_plus.in","r",stdin);
freopen("partial_order_plus.out","w",stdout);
scanf("%d%d",&n,&k); siz=int(sqrt(n*1.0));
for(int i=1;i<=n;i++) block[i]=(i-1)/siz+1;
for(int i=1;i<=n;i++) d[0].a[i]=i;
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
scanf("%d",&d[i].a[j]);
for(int i=0;i<=k;i++) build(i);
int ans=0;
for(int i=1;i<=n;i++){
bit t=d[0].get(i);
for(int j=0;j<=k;j++) t&=d[j].get(i);
ans+=t.count();
}
printf("%d\n",ans);
return 0;
}

K-D Tree

距离最近的mmm个点

点数量≤5000050000≤50000,m≤10m10m≤10

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
const int inf=1e4+5;
int key,root,n,m,q,k,mxd;
int sqr(int x)
{
return x*x;
}

struct point
{
int d[7];
friend int dis(point a,point b)
{
int s=0;
for (int i=0; i<k; i++)
s+=sqr(a.d[i]-b.d[i]);
return s;
}
} po;

struct node
{
point nw;
int son[2],mi[7],mx[7];
friend bool operator <(node a,node b)
{
return a.nw.d[key]<b.nw.d[key];
}
};

struct li
{
point a; int l;
friend bool operator <(li a, li b)
{
return a.l<b.l;
}
} mx;
set<li> st;

struct kdtree
{
node a[500010];
void init()
{

a[0].son[0]=a[0].son[1]=0;
for (int i=0; i<5; i++)
{
a[0].mx[i]=-inf;
a[0].mi[i]=inf;
}
}
void update(int x)
{
int l=a[x].son[0],r=a[x].son[1];
for (int i=0; i<k; i++)
{
a[x].mi[i]=min(a[x].nw.d[i],min(a[l].mi[i],a[r].mi[i]));
a[x].mx[i]=max(a[x].nw.d[i],max(a[l].mx[i],a[r].mx[i]));
}
}
int build(int l,int r,int cur)
{
if (l>r) return 0;
int m=(l+r)>>1;
key=cur; nth_element(a+l,a+m,a+r+1);
a[m].son[0]=build(l,m-1,(cur+1)%k);
a[m].son[1]=build(m+1,r,(cur+1)%k);
update(m);
return m;
}
int getmi(int x)
{
int s=0;
for (int i=0; i<k; i++)
s+=sqr(max(po.d[i]-a[x].mx[i],0)+max(a[x].mi[i]-po.d[i],0));
return s;
}
void ask(int q)
{
if (!q) return;
int tmp=dis(a[q].nw,po);
st.insert((li){a[q].nw,tmp});
if (st.size()>m)
{
set<li>::iterator it=st.end(); it--;
st.erase(it);
}
mxd=(*st.rbegin()).l;
int l=a[q].son[0],r=a[q].son[1],dl=2147483647,dr=2147483647;
if (l) dl=getmi(l);
if (r) dr=getmi(r);
if (dl<dr)
{
if (dl<mxd||st.size()<m) ask(l);
if (dr<mxd||st.size()<m) ask(r);
}
else {
if (dr<mxd||st.size()<m) ask(r);
if (dl<mxd||st.size()<m) ask(l);
}
}
} kd;

int main()
{
while (scanf("%d%d",&n,&k)!=EOF)
{
kd.init();
for (int i=1; i<=n; i++)
for (int j=0; j<k; j++)
scanf("%d",&kd.a[i].nw.d[j]);
root=kd.build(1,n,0);
scanf("%d",&q);
while (q--)
{
for (int i=0; i<k; i++)
scanf("%d",&po.d[i]);
scanf("%d",&m);
st.clear();
kd.ask(root);
printf("the closest %d points are:\n",m);
for (set<li>::iterator it=st.begin(); it!=st.end(); it++)
{
point ans=(*it).a;
for (int i=0; i<k; i++)
{
printf("%d",ans.d[i]);
if (i!=k-1) printf(" "); else puts("");
}
}
}
}
}

k远点对(二维)

给出NNN个点,求欧氏距离下的第KKK远点对

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
#define N 100005
#define inf 0x7fffffff
int n,m,root,Q;
struct KDtree
{
int min[2],max[2],d[2],l,r;
ll dis;
bool operator < (const KDtree &a) const
{
return dis<a.dis;
}
}t[N];
priority_queue <KDtree> q;

void updata(int x,int y)
{
t[x].min[0]=min(t[x].min[0],t[y].min[0]);
t[x].max[0]=max(t[x].max[0],t[y].max[0]);
t[x].min[1]=min(t[x].min[1],t[y].min[1]);
t[x].max[1]=max(t[x].max[1],t[y].max[1]);
}

int build(int l,int r,int now)
{
for (int i=l;i<=r;i++)
t[i].dis=t[i].d[now];
int mid=(l+r)/2;
nth_element(t+l,t+mid,t+r+1);
t[mid].min[0]=t[mid].max[0]=t[mid].d[0];
t[mid].min[1]=t[mid].max[1]=t[mid].d[1];
if (l<mid) t[mid].l=build(l,mid-1,1-now);
if (r>mid) t[mid].r=build(mid+1,r,1-now);
if (t[mid].l) updata(mid,t[mid].l);
if (t[mid].r) updata(mid,t[mid].r);
return mid;
}

ll dist(int x,int y)
{
return (ll)(t[x].d[0]-t[y].d[0])*(t[x].d[0]-t[y].d[0])+(ll)(t[x].d[1]-t[y].d[1])*(t[x].d[1]-t[y].d[1]);
}

ll get(int x)
{
ll ret=0;
ret+=max((ll)(t[Q].d[0]-t[x].min[0])*(t[Q].d[0]-t[x].min[0]),(ll)(t[x].max[0]-t[Q].d[0])*(t[x].max[0]-t[Q].d[0]));
ret+=max((ll)(t[Q].d[1]-t[x].min[1])*(t[Q].d[1]-t[x].min[1]),(ll)(t[x].max[1]-t[Q].d[1])*(t[x].max[1]-t[Q].d[1]));
return ret;
}

void solve(int x)
{
t[x].dis=-dist(x,Q);
if (q.size()<m) q.push(t[x]);
else
{
KDtree u=q.top();
if (u.dis>t[x].dis)
{
q.pop();
q.push(t[x]);
}
}
ll dl=inf,dr=inf;
if (t[x].l) dl=-get(t[x].l);
if (t[x].r) dr=-get(t[x].r);
if (dl<dr)
{
if (dl<q.top().dis||q.size()<m&&t[x].l) solve(t[x].l);
if (dr<q.top().dis||q.size()<m&&t[x].r) solve(t[x].r);
}else
{
if (dr<q.top().dis||q.size()<m&&t[x].r) solve(t[x].r);
if (dl<q.top().dis||q.size()<m&&t[x].l) solve(t[x].l);
}
}

int main()
{
scanf("%d%d",&n,&m);
m*=2;
for (int i=1;i<=n;i++)
scanf("%d%d",&t[i].d[0],&t[i].d[1]);
root=build(1,n,0);
for (int i=1;i<=n;i++)
{
Q=i;
solve(root);
}
printf("%lld",-q.top().dis);
return 0;
}

维护二维区间和

1 x y A 在坐标(x,y)(x,y)(x,y)增加权值A

2 x1 y1 x2 y2 输出x1 y1 x2 y2这个矩形内的数字和

3 终止程序运行

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
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 160010;
const int lim_siz = 2000;
int split[maxn],now;
int dem = 2;
struct Node{
int pos[2],val;
int minn[2],maxx[2],sum;
Node *ch[2];
void update(){
for(int d=0;d<dem;++d) minn[d] = min(pos[d],min(ch[0]->minn[d],ch[1]->minn[d]));
for(int d=0;d<dem;++d) maxx[d] = max(pos[d],max(ch[0]->maxx[d],ch[1]->maxx[d]));
sum = val + ch[0]->sum + ch[1]->sum;
}

}*null,*root,*op;
Node T[maxn];
inline bool cmp(const Node &a,const Node &b){
return a.pos[split[now]] < b.pos[split[now]];
}
inline void init(){
null = &T[0];
null->ch[0] = null->ch[1] = null;
null->val = 0;
for(int d=0;d<dem;++d){
null->pos[d] = 0;
null->minn[d] = 0x3f3f3f3f;
null->maxx[d] = -0x3f3f3f3f;
}root = null;
}
Node* build(int l,int r,int s){
if(l > r) return null;
int mid = (l+r)>> 1;
split[now = mid] = s % dem;
nth_element(T+l,T+mid,T+r+1,cmp);
Node *p = &T[mid];
p->ch[0] = build(l,mid-1,s+1);
p->ch[1] = build(mid+1,r,s+1);
p->update();return p;
}
int sav[maxn][2],sav_cnt,cnt;
int val[maxn],cmd,X1,Y1,X2,Y2,x;
int query(Node *p){
if(p == null) return 0;
if(p->minn[0] >= X1 && p->minn[1] >= Y1
&& p->maxx[0] <= X2 && p->maxx[1] <= Y2)
return p->sum;
else if(p->maxx[1] < Y1 || p->maxx[0] < X1
|| p->minn[0] > X2 || p->minn[1] > Y2)
return 0;
if( p->pos[0] >= X1 && p->pos[1] >= Y1
&& p->pos[0] <= X2 && p->pos[1] <= Y2)
return p->val + query(p->ch[0]) + query(p->ch[1]);
return query(p->ch[0]) + query(p->ch[1]);
}
int main(){
init();
int n;read(n);//read(n);
int lastans = 0;
while(1){
read(cmd);
if(cmd == 3) break;
if(cmd == 1){
read(X1);read(Y1);read(x);
X1 ^= lastans;Y1 ^= lastans;x ^= lastans;
sav[++sav_cnt][0] = X1;
sav[sav_cnt][1] = Y1;
val[sav_cnt] = x;
if(sav_cnt == lim_siz){
for(int i=1;i<=sav_cnt;++i){
T[cnt+i].minn[0] = T[cnt+i].maxx[0] = T[cnt+i].pos[0] = sav[i][0];
T[cnt+i].minn[1] = T[cnt+i].maxx[1] = T[cnt+i].pos[1] = sav[i][1];
T[cnt+i].val = val[i];
}root = build(1,cnt+=sav_cnt,1);
sav_cnt = 0;
}
}else{
read(X1);read(Y1);read(X2);read(Y2);
X1 ^= lastans;Y1 ^= lastans;
X2 ^= lastans;Y2 ^= lastans;
int ans = 0;
for(int i=1;i<=sav_cnt;++i){
if(sav[i][0] >= X1 && sav[i][1] >= Y1
&& sav[i][0] <= X2 && sav[i][1] <= Y2)
ans += val[i];
}
ans += query(root);
printf("%d\n",lastans = ans);
}
}
return 0;
}

统计某一区间的最大值(三维)

在[l,r][l,r][l,r]之间找一个在这个区间里只出现过一次且最大的数

对于每一个数维护三个维度:(自己的位置xxx,相同数前一个位置yyy,相同数后一个位置zzz)

我们要的是x>=lx>=lx>=l且x<=rx<=rx<=r且y<ly<ly<l且$ z>r$的最大数。

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
#define N 200003
int n,m,cmpd,root,pre[N],next[N],point[N],ans,lastans,x,y,val[N];
struct data {
int d[3],mx[3],mn[3],val,maxn;
int l,r;
}tr[N];
int tmp[10][10];
int cmp(data a,data b)
{
return a.d[cmpd]<b.d[cmpd];
}
void update(int now)
{
int l=tr[now].l; int r=tr[now].r;
for (int i=0;i<=2;i++){
if (l) tr[now].mx[i]=max(tr[now].mx[i],tr[l].mx[i]),
tr[now].mn[i]=min(tr[now].mn[i],tr[l].mn[i]);
if (r) tr[now].mx[i]=max(tr[now].mx[i],tr[r].mx[i]),
tr[now].mn[i]=min(tr[now].mn[i],tr[r].mn[i]);
}
if (l) tr[now].maxn=max(tr[l].maxn,tr[now].maxn);
if (r) tr[now].maxn=max(tr[r].maxn,tr[now].maxn);
}
int build(int l,int r,int d)
{
d%=3;
cmpd=d;
int mid=(l+r)/2;
nth_element(tr+l,tr+mid,tr+r+1,cmp);
for (int i=0;i<=2;i++)
tr[mid].mx[i]=tr[mid].mn[i]=tr[mid].d[i];
//cout<<tr[mid].d[0]<<" "<<tr[mid].d[1]<<" "<<tr[mid].d[2]<<endl;;
if (l<mid) tr[mid].l=build(l,mid-1,d+1);
if (r>mid) tr[mid].r=build(mid+1,r,d+1);
update(mid);
return mid;
}
int check(int now)
{
if (tr[now].mx[0]<x||tr[now].mn[0]>y) return 0;
if (tr[now].mn[1]>=x) return 0;
if (tr[now].mx[2]<=y) return 0;
return 1;
}
void query(int now)
{
if (tr[now].d[0]>=x&&tr[now].d[0]<=y&&tr[now].d[1]<x&&tr[now].d[2]>y)
ans=max(ans,tr[now].val);
int l=tr[now].l; int r=tr[now].r;
if (l&&tr[l].maxn>ans)
if (check(l)) query(l);
if (r&&tr[r].maxn>ans)
if (check(r)) query(r);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&val[i]);
memset(point,0,sizeof(point));
for (int i=1;i<=n;i++)
pre[i]=point[val[i]],point[val[i]]=i;
for (int i=1;i<=n;i++) point[i]=n+1;
for (int i=n;i>=1;i--)
next[i]=point[val[i]],point[val[i]]=i;
for (int i=1;i<=n;i++)
tr[i].d[0]=i,tr[i].d[1]=pre[i],tr[i].d[2]=next[i],tr[i].val=tr[i].maxn=val[i];
root=build(1,n,0);
lastans=0;
for (int i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
x=(x+lastans)%n+1;
y=(y+lastans)%n+1;
if (x>y) swap(x,y);
ans=0;
query(root);
printf("%d\n",ans);
lastans=ans;
}
}

倍增思想

一维倍增

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
int n,a[300010],f[300010][30],ans[300010];

int GCD(int x,int y)
{
int r=x%y;
while (r!=0) x=y,y=r,r=x%y;
return y;
}

void init()
{
for (int i=1;i<=n;i++)
f[i][0]=a[i];
for (int i=1;(1<<i)<=n;i++)
for (int j=1;j+(1<<i)-1<=n;j++)
f[j][i]=GCD(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}

int query(int l,int r)
{
int k=(int)(log(double(r-l+1))/log((double)2));
return GCD(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
cin>>n;
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
init();
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
const int maxn=1010,lgn =11,INF =1e9;
int mymax(int a,int b,int c,int d){return max(max(max(a,b),c),d);}
int mymin(int a,int b,int c,int d){return min(min(min(a,b),c),d);}
int mx[maxn][maxn][lgn],mn[maxn][maxn][lgn];
int Log[maxn],A,B,n;
void st_pre()
{
for(int k=1;k<=Log[min(A,B)];k++)
for(int i=1;i+(1<<k)-1<=A;i++)
for(int j=1;j+(1<<k)-1<=B;j++)
{
mx[i][j][k]=mymax(mx[i][j][k-1],mx[i+(1<<k-1)][j][k-1],mx[i][j+(1<<k-1)][k-1],mx[i+(1<<k-1)][j+(1<<k-1)][k-1]);
mn[i][j][k]=mymin(mn[i][j][k-1],mn[i+(1<<k-1)][j][k-1],mn[i][j+(1<<k-1)][k-1],mn[i+(1<<k-1)][j+(1<<k-1)][k-1]);
}
}
int st_max(int x1,int y1,int x2,int y2)
{
int k=Log[n];
return mymax(mx[x1][y1][k],mx[x2-(1<<k)+1][y1][k],mx[x1][y2-(1<<k)+1][k],mx[x2-(1<<k)+1][y2-(1<<k)+1][k]);
}
int st_min(int x1,int y1,int x2,int y2)
{
int k=Log[n];
return mymin(mn[x1][y1][k],mn[x2-(1<<k)+1][y1][k],mn[x1][y2-(1<<k)+1][k],mn[x2-(1<<k)+1][y2-(1<<k)+1][k]);
}
int main()
{
scanf("%d%d%d",&A,&B,&n);
for(int i=1;i<=A;i++)
for(int j=1;j<=B;j++)
{
int x; scanf("%d",&x);
mx[i][j][0]=mn[i][j][0]=x;
}
Log[1]=0; for(int i=2;i<=max(A,B);i++) Log[i]=Log[i/2]+1;
st_pre();
int ans=INF;
for(int i=1;i+n-1<=A;i++)
for(int j=1;j+n-1<=B;j++)
ans=min(ans,st_max(i,j,i+n-1,j+n-1)-st_min(i,j,i+n-1,j+n-1));
printf("%d\n",ans);
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
int n,m,S,c[100010],h[100010],to[200010],ne[200010],d[100010],p[200010][20];

void dfs(int u)
{
c[u]=1;
for (int i=h[u];i!=-1;i=ne[i])
{
if (!d[to[i]])
{
d[to[i]]=d[u]+1;
p[to[i]][0]=u;
dfs(to[i]);
c[u]+=c[to[i]];
}
}
}

void init()
{
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i<=n;i++)
if (p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1];
}

int lca(int x,int y)
{
if (d[x]<d[y]) swap(x,y);
int i;
for (i=0;(1<<i)<=d[x];i++);i--;
for (int j=i;j>=0;j--)
if (d[x]-(1<<j)>=d[y]) x=p[x][j];
if (x==y) return x;
for (int j=i;j>=0;j--)
if (p[x][j]!=-1 && p[x][j]!=p[y][j])
x=p[x][j],y=p[y][j];
return p[x][0];
}

void Add(int x,int y)
{
S++;to[S]=x;ne[S]=h[y];h[y]=S;
S++;to[S]=y;ne[S]=h[x];h[x]=S;
}

int Find(int x,int y)
{
y=d[x]-y;
int i;
for (i=0;(1<<i)<=d[x];i++);i--;
for (int j=i;j>=0;j--)
if (d[x]-(1<<j)>=y) x=p[x][j];
return x;
}

int main()
{
cin>>n;m=n-1;
memset(h,-1,sizeof(h));
memset(d,0,sizeof(d));
S=0;
int x,y,q;
while(m--) scanf("%d%d",&x,&y),Add(x,y);
d[1]=1;dfs(1);init();
return 0;
}

Top Tree

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
const int N = 100010 * 2, inf = ~0U >> 1;
struct tag
{
int a, b; //ax+b
tag() { a = 1, b = 0; }
tag(int x, int y) { a = x, b = y; }
bool ex() { return a != 1 || b; }
tag operator+(const tag &x) { return tag(a * x.a, b * x.a + x.b); }
};
int atag(int x, tag y) { return x * y.a + y.b; }
struct data
{
int sum, minv, maxv, size;
data() { sum = size = 0, minv = inf, maxv =-inf; }
data(int x) { sum = minv = maxv = x, size = 1; }
data(int a, int b, int c, int d) { sum = a, minv = b, maxv = c, size = d; }
data operator+(const data &x)
{
return data(sum + x.sum, min(minv, x.minv), max(maxv, x.maxv), size + x.size);
}
};
data operator+(const data &a, const tag &b)
{
return a.size ? data(a.sum * b.a + a.size * b.b, atag(a.minv, b), atag(a.maxv, b), a.size) : a;
}

int f[N], son[N][4], a[N], tot, rt, rub, ru[N];
bool rev[N], in[N];
int val[N];
data csum[N], tsum[N], asum[N];
tag ctag[N], ttag[N];
bool isroot(int x, int t)
{
if (t)
return !f[x] || !in[f[x]] || !in[x];
return !f[x] || (son[f[x]][0] != x && son[f[x]][1] != x) || in[f[x]] || in[x];
}
void rev1(int x)
{
if (!x)
return;
swap(son[x][0], son[x][1]);
rev[x] ^= 1;
}
void tagchain(int x, tag p)
{
if (!x)
return;
csum[x] = csum[x] + p;
asum[x] = csum[x] + tsum[x];
val[x] = atag(val[x], p);
ctag[x] = ctag[x] + p;
}
void tagtree(int x, tag p, bool t)
{
if (!x)
return;
tsum[x] = tsum[x] + p;
ttag[x] = ttag[x] + p;
if (!in[x] && t)
tagchain(x, p);
else
asum[x] = csum[x] + tsum[x];
}
void pb(int x)
{
if (!x)
return;
if (rev[x])
rev1(son[x][0]), rev1(son[x][1]), rev[x] = 0;
if (!in[x] && ctag[x].ex())
{
tagchain(son[x][0], ctag[x]);
tagchain(son[x][1], ctag[x]);
ctag[x] = tag();
}
if (ttag[x].ex())
{
tagtree(son[x][0], ttag[x], 0), tagtree(son[x][1], ttag[x], 0);
tagtree(son[x][2], ttag[x], 1), tagtree(son[x][3], ttag[x], 1);
ttag[x] = tag();
}
}
void up(int x)
{
tsum[x] = data();
for (int i = 0; i < 2; i++)
if (son[x][i])
tsum[x] = tsum[x] + tsum[son[x][i]];
for (int i = 2; i < 4; i++)
if (son[x][i])
tsum[x] = tsum[x] + asum[son[x][i]];
if (in[x])
{
csum[x] = data();
asum[x] = tsum[x];
}
else
{
csum[x] = data(val[x]);
for (int i = 0; i < 2; i++)
if (son[x][i])
csum[x] = csum[x] + csum[son[x][i]];
asum[x] = csum[x] + tsum[x];
}
}
int child(int x, int t)
{
pb(son[x][t]);
return son[x][t];
}
void rotate(int x, int t)
{
int y = f[x], w = (son[y][t + 1] == x) + t;
son[y][w] = son[x][w ^ 1];
if (son[x][w ^ 1])
f[son[x][w ^ 1]] = y;
if (f[y])
for (int z = f[y], i = 0; i < 4; i++)
if (son[z][i] == y)
son[z][i] = x;
f[x] = f[y];
f[y] = x;
son[x][w ^ 1] = y;
up(y);
}
void splay(int x, int t = 0)
{
int s = 1, i = x, y;
a[1] = i;
while (!isroot(i, t))
a[++s] = i = f[i];
while (s)
pb(a[s--]);
while (!isroot(x, t))
{
y = f[x];
if (!isroot(y, t))
{
if ((son[f[y]][t] == y) ^ (son[y][t] == x))
rotate(x, t);
else
rotate(y, t);
}
rotate(x, t);
}
up(x);
}
int newnode()
{
int x = rub ? ru[rub--] : ++tot;
son[x][2] = son[x][3] = 0;
in[x] = 1;
return x;
}
void setson(int x, int t, int y)
{
son[x][t] = y;
f[y] = x;
}
int pos(int x)
{
for (int i = 0; i < 4; i++)
if (son[f[x]][i] == x)
return i;
return 4;
}
void add(int x, int y)
{
if (!y)
return;
pb(x);
for (int i = 2; i < 4; i++)
if (!son[x][i])
{
setson(x, i, y);
return;
}
while (son[x][2] && in[son[x][2]])
x = child(x, 2);
int z = newnode();
setson(z, 2, son[x][2]);
setson(z, 3, y);
setson(x, 2, z);
splay(z, 2);
}
void del(int x)
{
if (!x)
return;
splay(x);
if (!f[x])
return;
int y = f[x];
if (in[y])
{
int s = 1, i = y, z = f[y];
a[1] = i;
while (!isroot(i, 2))
a[++s] = i = f[i];
while (s)
pb(a[s--]);
if (z)
{
setson(z, pos(y), child(y, pos(x) ^ 1));
splay(z, 2);
}
ru[++rub] = y;
}
else
{
son[y][pos(x)] = 0;
splay(y);
}
f[x] = 0;
}
int fa(int x)
{
splay(x);
if (!f[x])
return 0;
if (!in[f[x]])
return f[x];
int t = f[x];
splay(t, 2);
return f[t];
}
int access(int x)
{
int y = 0;
for (; x; y = x, x = fa(x))
{
splay(x);
del(y);
add(x, son[x][1]);
setson(x, 1, y);
up(x);
}
return y;
}
int lca(int x, int y)
{
access(x);
return access(y);
}
int root(int x)
{
access(x);
splay(x);
while (son[x][0])
x = son[x][0];
return x;
}
void makeroot(int x)
{
access(x);
splay(x);
rev1(x);
}
void link(int x, int y)
{
makeroot(x);
add(y, x);
access(x);
}
void cut(int x)
{
access(x);
splay(x);
f[son[x][0]] = 0;
son[x][0] = 0;
up(x);
}
void changechain(int x, int y, tag p)
{
makeroot(x);
access(y);
splay(y);
tagchain(y, p);
}
data askchain(int x, int y)
{
makeroot(x);
access(y);
splay(y);
return csum[y];
}
void changetree(int x, tag p)
{
access(x);
splay(x);
val[x] = atag(val[x], p);
for (int i = 2; i < 4; i++)
if (son[x][i])
tagtree(son[x][i], p, 1);
up(x);
splay(x);
}
data asktree(int x)
{
access(x);
splay(x);
data t = data(val[x]);
for (int i = 2; i < 4; i++)
if (son[x][i])
t = t + asum[son[x][i]];
return t;
}
int n, m, x, y, z, k, i, ed[N][2];
int main()
{
read(n); //n个点
read(m); //m个询问
tot = n;
for (i = 1; i < n; i++) //边
read(ed[i][0]), read(ed[i][1]);
for (i = 1; i <= n; i++) //点权
read(val[i]), up(i);
for (i = 1; i < n; i++)
link(ed[i][0], ed[i][1]);
read(rt);
makeroot(rt);
while (m--)
{
read(k);
if (k == 1)
{//换根
read(rt);
makeroot(rt);
}
if (k == 9)
{ //x的父亲变成y
read(x), read(y);
if (lca(x, y) == x) continue;
cut(x);
link(y, x);
makeroot(rt);
}
if (k == 0)
{ //子树赋值
read(x), read(y);
changetree(x, tag(0, y));
}
if (k == 5)
{ //子树加
read(x), read(y);
changetree(x, tag(1, y));
}
if (k == 3)
{ //子树最小值
read(x);
printf("%d\n", asktree(x).minv);
}
if (k == 4)
{ //子树最大值
read(x);
printf("%d\n", asktree(x).maxv);
}
if (k == 11)
{ //子树和
read(x);
printf("%d\n", asktree(x).sum);
}
if (k == 2)
{ //链赋值
read(x), read(y), read(z);
changechain(x, y, tag(0, z));
makeroot(rt);
}
if (k == 6)
{ //链加
read(x), read(y), read(z);
changechain(x, y, tag(1, z));
makeroot(rt);
}
if (k == 7)
{ //链最小值
read(x), read(y);
printf("%d\n", askchain(x, y).minv);
makeroot(rt);
}
if (k == 8)
{ //链最大值
read(x), read(y);
printf("%d\n", askchain(x, y).maxv);
makeroot(rt);
}
if (k == 10)
{ //链和
read(x), read(y);
printf("%d\n", askchain(x, y).sum);
makeroot(rt);
}
}
}

字符串处理

AC自动机

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
141
142
143
144
#include<cstring>
#include<queue>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
const int SIGMA_SIZE = 26;
const int MAXNODE = 11000;
const int MAXS = 150 + 10;

struct AhoCorasickAutomata {
int ch[MAXNODE][SIGMA_SIZE];
int f[MAXNODE]; // fail函数
int val[MAXNODE]; // 每个字符串的结尾结点都有一个非0的val
int last[MAXNODE]; // 输出链表的下一个结点
int match[MAXNODE]; // 表示这个点是结点
int cnt[MAXS]; //用来统计模式串被找到了几次
int sz;

void init() {
sz = 1;
memset(ch[0], 0, sizeof(ch[0]));
memset(cnt, 0, sizeof(cnt));
memset(match, 0, sizeof(match));
}

// 字符c的编号
int idx(char c) {
return c-'a';
}

// 插入字符串。v必须非0
void insert(char *s, int v) {
int u = 0, n = strlen(s);
for(int i = 0; i < n; i++) {
int c = idx(s[i]);
if(!ch[u][c]) {
memset(ch[sz], 0, sizeof(ch[sz]));
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] = v;
}

// 递归打印以结点j结尾的所有字符串
void print(int j) {
if(j) {
cnt[val[j]]++;
//match[j] = 1;
print(last[j]);
}
}

// 在T中找模板
int find(char* T) {
int n = strlen(T);
int j = 0; // 当前结点编号,初始为根结点
for(int i = 0; i < n; i++) { // 文本串当前指针
int c = idx(T[i]);
j = ch[j][c];
if(val[j]) print(j);
else if(last[j]) print(last[j]); // 找到了!
}
}

// 计算fail函数
void getFail() {
queue<int> q;
f[0] = 0;
// 初始化队列
for(int c = 0; c < SIGMA_SIZE; c++) {
int u = ch[0][c];
if(u) { f[u] = 0; q.push(u); last[u] = 0; }
}
// 按BFS顺序计算fail
while(!q.empty()) {
int r = q.front(); q.pop();
for(int c = 0; c < SIGMA_SIZE; c++) {
int u = ch[r][c];
if(!u) {ch[r][c] = ch[f[r]][c];continue;}
q.push(u);
int v = f[r];
while(v && !ch[v][c]) v = f[v];
f[u] = ch[v][c];
last[u] = val[f[u]] ? f[u] : last[f[u]];
}
}
/* *when Matrix need
for(int i = 0; i < sz; i++) {
if(val[i]) print(i);
else if(last[i]) print(i);
}
*/
/* 统计长度为n的串有多种可能不出现模板串,需要Matrix
int doit(int n) {
matrix A(sz, sz);
for(int i = 0; i < sz; i++) {
if(match[i]) continue;
for(int c = 0; c < SIGMA_SIZE; c++) {
if(!match[ch[i][c]]) A[i][ch[i][c]]++;
}
}
A = A ^ n;
int ans = 0;
for(int i = 0; i < sz; i++) {
ans += A[0][i];
ans %= MOD;
}
return ans;
}
*/
}

};

AhoCorasickAutomata ac;
char text[1000001], P[151][80];
int n, T;
map<string,int> ms;

int main()
{
while(scanf("%d", &n) == 1 && n)
{
ac.init();
for(int i = 1; i <= n; i++)
{
scanf("%s", P[i]);
ac.insert(P[i], i);
}
ac.getFail();
scanf("%s", text);
ac.find(text);
int best = -1;
for(int i = 1; i <= n; i++)
if(ac.cnt[i] > best) best = ac.cnt[i];
printf("%d\n", best);
for(int i = 1; i <= n; i++)
if(ac.cnt[ms[string(P[i])]] == best) printf("%s\n", P[i]);
}
return 0;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
char a1[2000000],a2[2000000];
int kmp[2000000];
int main()
{
scanf("%s%s",a1,a2);
kmp[0]=kmp[1]=0;//前一位,两位失配了,都只可能将第一位作为新的开头
int len1=strlen(a1),len2=strlen(a2);
int k;
k=0;
for(int i=1;i<len2;i++)//自己匹配自己
{
while(k&&a2[i]!=a2[k])k=kmp[k];//找到最长的前后缀重叠长度
kmp[i+1]=a2[i]==a2[k]?++k:0;//不相等的情况,即无前缀能与后缀重叠,直接赋值位0(注意是给下一位,因为匹配的是下一位适失配的情况)
}
k=0;
for(int i=0;i<len1;i++)
{
while(k&&a1[i]!=a2[k])k=kmp[k];//如果不匹配,则将利用kmp数组往回跳
k+=a1[i]==a2[k]?1:0;//如果相等了,则匹配下一位
if(k==len2)printf("%d\n",i-len2+2);//如果已经全部匹配完毕,则输出初始位置
}
for(int i=1;i<=len2;i++)printf("%d ",kmp[i]);//输出f数组
return 0;
}

拓展KMP

求s1的前缀和s2的后缀最大匹配。

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
#define maxn 111111
char a[maxn],b[maxn];
int nex[maxn];
int main()
{
while(scanf("%s%s",a,b)!=EOF)
{
int len1=strlen(a);
int len2=strlen(b);
int len=min(len1,len2);//最大匹配长度必须不大于两串串长较小值
for(int i=len1,j=0;i<len1+len2;i++,j++)//将a串b串合并
a[i]=b[j];
int la=len1+len2;//总串长
for(int i=0,j=-1;i<=la;i++,j++)//求next数组
{
nex[i]=j;
while(~j&&a[i]!=a[j])
j=nex[j];
}
while(nex[la]>len)
la=nex[la];
if(nex[la]==0)//最大匹配长度为0直接输出0
printf("0\n");
else
{
for(int i=0;i<nex[la];i++)//输出最大匹配
printf("%c",a[i]);
printf(" %d\n",nex[la]);//输出最大匹配长度
}
}
return 0;
}

后缀数组

第一行nnn个整数,第iii个整数表示排名为iii的后缀的第一个字符在原串中的位置。

第二行n−1n−1n−1个整数,第iii个整数表示排名为iii和排名为i+1i+1i+1的后缀的最长公共前缀的长度。

时间复杂度O(n)O(n)O(n)

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
int n,m,s,b[200010],c[200010],d[200010];
char sx[200010],sy[200010];
struct data
{
int len,fa,letter[26],tree[26],id,flag;
}a[200010];
int sa[200010],rank[200010],RANK;

void Extend(int x,int p)
{
s++;int q=s;a[q].len=a[p].len+1;
while (p!=0 && a[p].letter[x]==0)
a[p].letter[x]=q,p=a[p].fa;
if (p==0) {a[q].fa=1;return ;}
int np=a[p].letter[x];
if (a[np].len==a[p].len+1) a[q].fa=np;
else
{
s++;int nq=s;a[nq].len=a[p].len+1;
for (int i=0;i<26;i++)
a[nq].letter[i]=a[np].letter[i];
a[nq].id=a[np].id;
a[nq].fa=a[np].fa;a[np].fa=nq;a[q].fa=nq;
while (p!=0&&a[p].letter[x]==np)
a[p].letter[x]=nq,p=a[p].fa;
}
}

void Insert(char x[])
{
int y=strlen(x);
s=1;int z=1;
for (int i=y-1;i>=0;i--)
Extend(x[i]-'a',z),z=a[z].letter[x[i]-'a'],a[z].id=i+1,d[i+1]=z,a[z].flag=1;
}

void dfs(int x)
{
if(a[x].id!=0 && a[x].flag) sa[++RANK]=a[x].id,rank[a[x].id]=RANK;
for (int i=0;i<26;i++)
if (a[x].tree[i]!=0) dfs(a[x].tree[i]);
}

void build()
{
for (int i=1;i<=s;i++)
c[a[i].len]++;
for (int i=1;i<=s;i++)
c[i]+=c[i-1];
for (int i=1;i<=s;i++)
b[c[a[i].len]--]=i;
for (int i=s;i>=1;i--)
{
int p=b[i];
a[a[p].fa].tree[sx[a[p].id+a[a[p].fa].len-1]-'a']=p;
}
RANK=0;
dfs(1);
}

LL Query(int x,int y)
{
if (x==y) return a[x].len;
if (a[x].len>a[y].len) return Query(a[x].fa,y);
else return Query(x,a[y].fa);
}

int main()
{
n=read(sx);n=strlen(sx);
Insert(sx);
build();
for (int i=1;i<n;i++)
print(sa[i]),putchar(' ');
print(sa[n]);puts("");
for (int i=1;i<n-1;i++)
print(Query(d[sa[i]],d[sa[i+1]])),putchar(' ');
if (n>1) print(Query(d[sa[n-1]],d[sa[n]])),puts("");
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
int n,m,s,b[500010],c[500010];
char sx[250010],sy[250010];
struct data
{
int len,fa,letter[26],res,x;
}a[500010];
const int inf=500010;
void Extend(int x,int p)
{
s++;int q=s;a[q].len=a[p].len+1;
while (p!=0 && a[p].letter[x]==0)
a[p].letter[x]=q,p=a[p].fa;
if (p==0) {a[q].fa=1;return ;}
int np=a[p].letter[x];
if (a[np].len==a[p].len+1) a[q].fa=np;
else
{
s++;int nq=s;a[nq].len=a[p].len+1;
for (int i=0;i<26;i++)
a[nq].letter[i]=a[np].letter[i];
a[nq].fa=a[np].fa;a[np].fa=nq;a[q].fa=nq;
while (p!=0&&a[p].letter[x]==np)
a[p].letter[x]=nq,p=a[p].fa;
}
}
void Insert(char x[])
{
int y=strlen(x);
s=1;int z=1;
for (int i=0;i<y;i++)
Extend(x[i]-'a',z),z=a[z].letter[x[i]-'a'];
memset(c,0,sizeof(c));
for (int i=1;i<=s;i++)
a[i].res=a[i].len,c[a[i].len]++;
for (int i=1;i<=s;i++)
c[i]+=c[i-1];
for (int i=1;i<=s;i++)
b[c[a[i].len]--]=i;
}
void Query(char x[])
{
int res=0,p=1,z,y=strlen(x);
for (int i=0;i<y;i++)
{
z=x[i]-'a';
while (p!=0&&a[p].letter[z]==0) p=a[p].fa,res=a[p].len;
if (a[p].letter[z]!=0) res++,p=a[p].letter[z];
else res=0,p=1;
a[p].x=max(a[p].x,res);
}
for (int i=s;i>=1;i--)
{
p=b[i];
a[a[p].fa].x=max(a[a[p].fa].x,a[p].x);
a[p].res=min(a[p].res,a[p].x);
a[p].x=0;
}
}
int main()
{
n=read(sx);
Insert(sx);
while (read(sy))
Query(sy);
int ans=0;
for (int i=1;i<=s;i++)
ans=max(ans,a[i].res);
print(ans),puts("");
return 0;
}

求第kkk小字符串

不同位置相同子串算多个

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
int n,m,s,b[1000010],c[1000010];
char sx[1000010],sy[1000010];
struct data
{
int fa,letter[26];
LL len,child,res;
}a[1000010];
void Extend(int x,int p)
{
s++;int q=s;a[q].len=a[p].len+1;
while (p!=0 && a[p].letter[x]==0)
a[p].letter[x]=q,p=a[p].fa;
if (p==0) {a[q].fa=1;return ;}
int np=a[p].letter[x];
if (a[np].len==a[p].len+1) a[q].fa=np;
else
{
s++;int nq=s;a[nq].len=a[p].len+1;
for (int i=0;i<26;i++)
a[nq].letter[i]=a[np].letter[i];
a[nq].fa=a[np].fa;a[np].fa=nq;a[q].fa=nq;
while (p!=0&&a[p].letter[x]==np)
a[p].letter[x]=nq,p=a[p].fa;
}
}
void Insert(char x[])
{
int y=strlen(x);
s=1;int z=1;
for (int i=0;i<y;i++)
Extend(x[i]-'a',z),z=a[z].letter[x[i]-'a'],a[z].child++;
memset(c,0,sizeof(c));
for (int i=1;i<=s;i++)
a[i].res=0,c[a[i].len]++;
for (int i=1;i<=s;i++)
c[i]+=c[i-1];
for (int i=1;i<=s;i++)
b[c[a[i].len]--]=i;
}
void init()
{
for (int i=s;i>=1;i--)
{
int p=b[i];
if (n==1) a[a[p].fa].child+=a[p].child;
else a[p].child=1;
}
for (int i=s;i>=1;i--)
{
int p=b[i];a[p].res=a[p].child;
for (int j=0;j<26;j++)
a[p].res+=a[a[p].letter[j]].res;
}
}
void Query(int y,int x)
{
if (x<=0) return ;
int i=0;
while(i<26&&a[a[y].letter[i]].res<x)
x-=a[a[y].letter[i]].res,i++;
if (i==26) {puts("-1");return ;}
else {putchar(i+'a'),Query(a[y].letter[i],x-a[a[y].letter[i]].child);}
}
int main()
{
n=read(sx);
Insert(sx);
read(n);read(m);
init();
a[1].child=0;
Query(1,m);
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
namespace SuffixAutomation {
const int MAXN = 180005;
struct Node {
Node *next[26], *fa;
int max, cnt;
Node(int max = 0) : max(max) {}
Node(int max, Node *p) {
*this = *p, this->max = max;
}
inline void *operator new(size_t);
} pool[MAXN], *cur = pool, *root, *last;
inline void *Node::operator new(size_t) {
return cur++;
}
inline void init() {
root = last = new Node();
}
inline Node *extend(int c, Node *p) {
Node *np = new Node(p->max + 1);
while (p && !p->next[c]) p->next[c] = np, p = p->fa;
if (!p) {
np->fa = root;
} else {
Node *q = p->next[c];
if (q->max == p->max + 1) {
np->fa = q;
} else {
Node *nq = new Node(p->max + 1, q);
q->fa = np->fa = nq;
while (p && p->next[c] == q) p->next[c] = nq, p = p->fa;
}
}
return np;
}
std::vector<Node *> buc[MAXN];
typedef std::pair<Node *, int> Pair;
std::vector<Pair> edge[MAXN];
/*预处理从每个节点出发,还有多少不同的子串可以到达。*/
inline void prepare(const char *s, const int n) {
for (Node *p = pool; p != cur; p++) p->cnt = 1, buc[p->max].push_back(p);
for (register int i = n; i >= 0; i--) {
for (auto p : buc[i]) {
for (register int j = 0; j < 26; j++) {
if (p->next[j]) {
edge[p - pool].push_back(Pair(p->next[j], j));
/*这里是预处理,保证时间复杂度,并不是 endPos 集合,记录的是当前节点不同子串个数*/
p->cnt += p->next[j]->cnt;
}
}
}
}
}
inline void dfs(Node *p, int k) {
if (--k == 0) return;
for (auto i : edge[p - pool]) {
if (i.first->cnt < k) {
k -= i.first->cnt;
} else {
putchar('a' + i.second), dfs(i.first, k);
break;
}
}
}
inline void solve() {
static char s[MAXN];
scanf("%s", s);
register int n = strlen(s);
init();
for(register int i = 0; i < n; i++) last = extend(s[i] - 'a', last);
prepare(s, n);
register int q;
scanf("%d", &q);
for (register int i = 1, k; i <= q; i++) {
scanf("%d", &k), dfs(root, k + 1), putchar('\n');
}
}
}
int main() {
SuffixAutomation::solve();
}

不同子串的出现次数

f[i]f[i]f[i]指长度为iii的串出现次数的最大值,输出f[1]f[1]f[1]…f[n]f[n]f[n]

一个节点sss的出现次数是endpos(s)endpos(s)endpos(s),一个节点的长度范围是[len(s−>fa)+1,len(s)][len(s->fa)+1, len(s)][len(s−>fa)+1,len(s)]

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
namespace SuffixAutomation {
const int MAXN = 500005;
struct Node {
Node *next[26], *fa;
int max, endPosSize;
Node(int max = 0) : max(max) {}
Node(int max, Node *p) {
*this = *p, this->max = max;
}
inline void *operator new(size_t);
} pool[MAXN], *cur = pool, *root, *last;
inline void *Node::operator new(size_t) {
return cur++;
}
inline void init() {
root = last = new Node();
}
inline Node *extend(int c, Node *p) {
Node *np = new Node(p->max + 1);
while (p && !p->next[c]) p->next[c] = np, p = p->fa;
if (!p) {
np->fa = root;
} else {
Node *q = p->next[c];
if (q->max == p->max + 1) {
np->fa = q;
} else {
Node *nq = new Node(p->max + 1, q);
q->fa = np->fa = nq;
while (p && p->next[c] == q) p->next[c] = nq, p = p->fa;
}
}
return np;
}
inline void getEndPosSize(const char *s, const int n) {
/*将Suffix Link 上的所有叶子节点的endPosSize设置为1*/
Node *p = root;
for (register int i = 0; i < n; i++)
p = p->next[*s++ - 'a'], p->endPosSize++;
/*按照 len 从大到小的顺序更新*/
static std::vector<Node *> buc[MAXN];
static int ans[MAXN];
for (Node *p = pool; p != cur; p++) buc[p->max].push_back(p);
for (register int i = n; i; i--) {
for (auto p : buc[i]) {
ans[i] = std::max(ans[i], p->endPosSize); //这里做更新
p->fa->endPosSize += p->endPosSize;
}
}
for (register int i = n - 1; i; i--) ans[i] = std::max(ans[i], ans[i + 1]); //这道题目的特殊优化
for (register int i = 1; i <= n; i++) std::cout << ans[i] << "\n";
}
inline void solve() {
init();
static char s[MAXN];
scanf("%s", s);
register int n = strlen(s);
for (register int i = 0; i < n; i++)
last = extend(s[i] - 'a', last);
getEndPosSize(s, n);
}
}
int main() {
SuffixAutomation::solve();
return 0;
}

最长不重叠重复子串

“主题”是整个音符序列的一个子串,它需要满足如下条件:

1.长度至少为 5 个音符。

2.在乐曲中重复出现。(可能经过转调,“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)

3.重复出现的同一主题不能有公共部分。

对于转调,做一次差分,然后回归此问题

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
namespace SuffixAutomation {
const int MAXN = 20005;
struct Node {
Node *fa, *next[175];
int max, minPos, maxPos;
Node(int max = 0) : max(max), minPos(20000), maxPos(0), fa(NULL) {
memset(next, 0, sizeof(next));
}
Node(int max, Node *p) {
*this = *p, this->max = max;
}
inline void *operator new(size_t);
} pool[MAXN << 1], *cur = pool, *root, *last;
int n, a[MAXN];
std::vector<Node *> buc[MAXN];
inline void *Node::operator new(size_t) {
return cur++;
}
inline void init() {
cur = pool;
root = last = new Node();
for (register int i = 0; i <= n; i++) buc[i].clear();
}
inline Node *extend(int c, Node *p) {
Node *np = new Node(p->max + 1);
while (p && !p->next[c]) p->next[c] = np, p = p->fa;
if (!p) {
np->fa = root;
} else {
Node *q = p->next[c];
if (q->max == p->max + 1) {
np->fa = q;
} else {
Node *nq = new Node(p->max + 1, q);
q->fa = np->fa = nq;
while (p && p->next[c] == q) p->next[c] = nq, p = p->fa;
}
}
return np;
}
inline int getAns() {
register int res = 0;
Node *p = root;
p->minPos = p->maxPos = 0;
for (register int i = 0; i < n; i++)
p = p->next[a[i]], p->maxPos = p->minPos = i + 1;
for (Node *i = pool; i != cur; i++) buc[i->max].push_back(i);
for (register int i = n; i; i--) {
for (register int j = 0; j < buc[i].size(); j++) {
Node *tmp = buc[i][j];
res = std::max(res, std::min(tmp->max, tmp->maxPos - tmp->minPos - 1));
tmp->fa->minPos = std::min(tmp->fa->minPos, tmp->minPos);
tmp->fa->maxPos = std::max(tmp->fa->maxPos, tmp->maxPos);
}
}
return res < 4 ? 0 : res + 1;
}
inline void solve() {
while (scanf("%d", &n), n) {
for (register int i = 0; i < n; i++) scanf("%d", a + i);
n--;
for (register int i = 0; i < n; i++) a[i] = a[i + 1] - a[i] + 87;
init();
for (register int i = 0; i < n; i++) last = extend(a[i], last);
std::cout << getAns() << "\n";
}
}
}
int main() {
SuffixAutomation::solve();
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
namespace SuffixAutomation {
const int MAXN = 50000;
struct Node {
Node *fa, *next[128];
int max;
Node(int max = 0) : max(max), fa(NULL) {
memset(next, 0, sizeof(next));
}
Node(int max, Node *q) {
*this = *q, this->max = max;
}
inline void *operator new(size_t);
} pool[MAXN + 1 << 1], *cur = pool, *root, *last;
inline void *Node::operator new(size_t) {
return cur++;
}
int ans;
inline void init() {
cur = pool;
ans = 0;
root = last = new Node();
}
inline Node *extend(int c, Node *p) {
Node *np = new Node(p->max + 1);
while (p && !p->next[c]) p->next[c] = np, p = p->fa;
if (!p) {
np->fa = root;
} else {
Node *q = p->next[c];
if (q->max == p->max + 1) {
np->fa = q;
} else {
Node *nq = new Node(p->max + 1, q);
q->fa = np->fa = nq;
while (p && p->next[c] == q) p->next[c] = nq, p = p->fa;
}
}
ans += np->max - np->fa->max;
return np;
}
inline void solve() {
register int n;
scanf("%d", &n);
for (register int i = 0; i < n; i++) {
static char s[MAXN];
scanf("%s", s);
init();
register int len = strlen(s);
for (register int i = 0; i < len; i++) last = extend(s[i], last);
std::cout << ans << "\n";
}
}
}
int main() {
SuffixAutomation::solve();
return 0;
}

后缀平衡树

一棵根节点为111的树,每个节点代表一个字符

对于每个节点求这个节点到根节点路径上的不同子串的个数

输出出N个数,表示节点i到根节点路径上的不同子串的个数

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
const int N=1e5+10;
const int bas=31;
int hs[N],M[N];
int n,len,ans,Ans[N];
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
struct Suffix_Balanced_ScapeGoat_Tree{
int lx[N],rx[N],rt,size[N],s[N],cnt,Q[N],tail;
ll tag[N];
int get(int i,int l){return hs[i]-hs[i-l]*M[l];}
int qlcp(int x,int y){
int l=0,r=min(x,y);
while(l<r){
int mid=(l+r)>>1;
if(get(x,mid+1)==get(y,mid+1))l=mid+1;else r=mid;
}
return l;
}
inline bool cmp(int x,int y){int l=qlcp(x,y);return s[x-l]<s[y-l];}
inline int merge(int x,int y){
if(!x||!y)return x|y;
if(size[x]>size[y]){size[x]+=size[y];rx[x]=merge(rx[x],y);return x;}
else{size[y]+=size[x];lx[y]=merge(x,lx[y]);return y;}
}
inline int build(int ls,int rs,ll l,ll r){
if(ls>rs)return 0;
int mid=(ls+rs)>>1;ll midv=(l+r)>>1;int x=Q[mid];tag[x]=midv;
lx[x]=build(ls,mid-1,l,midv);rx[x]=build(mid+1,rs,midv,r);
size[x]=rs-ls+1;return x;
}
inline void dfs(int x){if(lx[x])dfs(lx[x]);Q[++tail]=x;if(rx[x])dfs(rx[x]);}
inline int rebuild(int x,ll l,ll r){
tail=0;dfs(x);return build(1,tail,l,r);
}
inline int ins(int x,ll l,ll r,int val){
if(!x){
size[++cnt]=1;lx[cnt]=rx[cnt]=0;tag[cnt]=(l+r)>>1;
return cnt;
}
size[x]++;
if(cmp(x,val)){
rx[x]=ins(rx[x],tag[x],r,val);
if(size[rx[x]]>0.65*size[x])x=rebuild(x,l,r);
}
else{
lx[x]=ins(lx[x],l,tag[x],val);
if(size[lx[x]]>0.65*size[x])x=rebuild(x,l,r);
}
return x;
}
inline int del(int x,int val){
if(x==val)return merge(lx[x],rx[x]);
size[x]--;
if(tag[x]<tag[val])rx[x]=del(rx[x],val);
else lx[x]=del(lx[x],val);
return x;
}
inline int queryrk(int key){
int x=rt,ans=0;
while(1){
int i=size[lx[x]]+1;
if(key==x)return ans+i;
if(tag[x]<tag[key])x=rx[x],ans+=i;else x=lx[x];
}
}
inline int find(int key){
int x=rt;
while(1){
int i=size[lx[x]]+1;
if(key==i)return x;
if(key>i)x=rx[x],key-=i;else x=lx[x];
}
}
inline void del(int x){
int rk=queryrk(x),y=find(rk-1),z=find(rk+1);
ans-=qlcp(x,y)+qlcp(x,z)-qlcp(y,z);
rt=del(rt,x);cnt--;len--;
}
inline void ins(int x){
s[++len]=x;hs[len]=hs[len-1]*bas+x;
rt=ins(rt,0,1LL<<62,len);
if(len<3)return;
int rk=queryrk(len),y=find(rk-1),z=find(rk+1);
ans+=qlcp(len,y)+qlcp(len,z)-qlcp(y,z);
}
}T;
char str[N];
struct Edge{int u,v,next;}G[N<<1];int head[N],tot=0;
inline void addedge(int u,int v){
G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot;
G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot;
}
inline void dfs(int u,int fa){
T.ins(str[u]-'a'+1);Ans[u]=(len-1)*(len-2)/2-ans;
for(int i=head[u];i;i=G[i].next){
if(G[i].v!=fa)dfs(G[i].v,u);
}
T.del(len);
}
int main(){
freopen("balsuffix.in","r",stdin);
freopen("balsuffix.out","w",stdout);
M[0]=1;
for(int i=1;i<N;i++)M[i]=M[i-1]*bas;
T.ins(27);T.ins(0);int T=read();
while(T--){
n=read();for(int i=1;i<=n;i++)head[i]=0;tot=0;
for(int i=1;i<n;i++){
int u=read(),v=read();addedge(u,v);
}
scanf("%s",str+1);
dfs(1,0);
for(int i=1;i<=n;i++)printf("%d\n",Ans[i]);
}
}

Palindromic树

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
const int maxn = 300010*2;  
const int ALP = 26;

struct PAM{
int next[maxn][ALP];
int fail[maxn] ;//fail指针,失配后跳转到fail指针指向的节点
int cnt[maxn] ; //表示节点i表示的本质不同的串的个数(建树时求出的不是完全的,最后count()函数跑一遍以后才是正确的)
int num[maxn] ; //表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数
int len[maxn] ;//len[i]表示节点i表示的回文串的长度(一个节点表示一个回文串)
int s[maxn] ;//存放添加的字符
int last ;//指向新添加一个字母后所形成的最长回文串表示的节点。
int n ;//表示添加的字符个数。
int p ;//表示添加的节点个数。

int newnode(int l){
for(int i=0;i<ALP;i++)
next[p][i]=0;
cnt[p]=num[p]=0;
len[p]=l;
return p++;
}
void init(){
p = 0;
newnode(0);
newnode(-1);
last = 0;
n = 0;
s[n] = -1;
fail[0] = 1;
}
int get_fail(int x){
while(s[n-len[x]-1] != s[n]) x = fail[x];
return x;
}
void add(int c){
c = c-'a';
s[++n] = c;
int cur = get_fail(last);
if(!next[cur][c]){
int now = newnode(len[cur]+2); //注意字符串长度为1的是由-1拓展过来的,要特判
fail[now] = next[get_fail(fail[cur])][c];
next[cur][c] = now;
num[now] = num[fail[now]] + 1;
}
last = next[cur][c];
cnt[last]++;
}
void count(){
for(int i=p-1;i>=0;i--)
cnt[fail[i]] += cnt[i];
}
}pam;

char s[maxn];
int main(){
scanf("%s",s);
int len = strlen(s);
pam.init();
for(int i=0;i<len;i++)
{
pam.add(s[i]);
}
pam.count();
long long ret = 0;
for(int i=2;i<pam.p;i++) //遍历所有的回文串
{
ret = max((long long)pam.len[i]*pam.cnt[i],ret);
}
cout<<ret<<endl;
return 0;
}

遍历

对于 A 中的每个回文子串,B 中和该子串相同的子串个数的总和

1
2
3
4
5
6
7
8
9
ll dfs(int an,int bn){  
ll ret = 0;
for(int i=0;i<ALP;i++) if(pam1.next[an][i]!=0 && pam2.next[bn][i]!=0)
ret += (ll)pam1.cnt[pam1.next[an][i]] * pam2.cnt[pam2.next[bn][i]]
+ dfs(pam1.next[an][i],pam2.next[bn][i]);
return ret;
}

ll ret = dfs(0,0) + dfs(1,1);

最小表示法

给出一个循环字符串,输出最小字典序的开始下标

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
const int MAXN=100000+7;
char s[MAXN];
int n;
int get_minstring()
{
int len=n;
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len)
{
int t=s[(i+k)%len]-s[(j+k)%len];//t值为两个字符比较的结果,而(i+k)%len是因为i+k会超过len又因为是循环同构串所以要%len。同理(j+k)%len也是一样的道理。
if(t==0)
k++;
else
{
if(t>0)
i+=k+1;
else
j+=k+1;
if(i==j)
j++;
k=0;
}
}
return min(i,j);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%s",&n,s);
printf("%d\n",get_minstring());
}
}

图论

k短路

Dijkstra

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
struct Edge
{
int to;
int value;
int next;
bool operator < (const Edge &t) const
{
return t.value < value;
}
};
struct Edge1
{
int to;
int value;
int next;
};
struct Node
{
int to;
int f, g;
bool operator < (const Node &t) const
{
if(t.f==f)
return t.g < g;
return t.f < f;
}
};
Edge edge[100010]; //存储边与原图反向的图
Edge1 edge1[100010]; //存储原图
int adj[1010], adj1[1010], visited[1010], dis[1010], edgeNum, edgeNum1;
int N, M;

void Dijkstra(int start)
{
int k;
Edge t, cur;
priority_queue<Edge> PQ;
for(k=0; k<N; k++)
{
visited[k] = 0;
dis[k] = INT_MAX;
}
t.to = start; //起始顶点
t.next = -1;
t.value = 0;
dis[start] = 0; //自己到自己路径为0
PQ.push(t);
visited[start] = 1; //标记以入队
while(!PQ.empty())
{
cur = PQ.top(); //出队
PQ.pop();
visited[cur.to] = 0; //标记出队
for(int tmp = adj[cur.to]; tmp != -1; tmp = edge[tmp].next)
{
if(dis[edge[tmp].to] > dis[cur.to] + edge[tmp].value)
{
dis[edge[tmp].to] = dis[cur.to] + edge[tmp].value;
if(visited[edge[tmp].to] == 0)
{
PQ.push(edge[tmp]);
visited[edge[tmp].to] = 1;
}
}
}
}
}

int A_star(int start, int end, int k)
{
Node e, ne;
int cnt = 0;
priority_queue<Node> PQ;
if(start==end)
k++;
if(dis[start]==INT_MAX) //无法到达终点
return -1;
e.to = start;
e.g = 0;
e.f = e.g + dis[e.to];
PQ.push(e);
while(!PQ.empty())
{
e = PQ.top();
PQ.pop();
if(e.to==end)
cnt++; //第cnt短路
if(cnt==k)
return e.g;
for(int i=adj1[e.to]; i!=-1; i=edge1[i].next)
{
ne.to = edge1[i].to;
ne.g = e.g + edge1[i].value;
ne.f = ne.g + dis[ne.to];
PQ.push(ne);
}
}
return -1;
}

void addEdge(int a, int b, int len) //反向图添加边
{
edge[edgeNum].to = b;
edge[edgeNum].next = adj[a];
edge[edgeNum].value = len;
adj[a] = edgeNum++;
}

void addEdge1(int a, int b, int len) //原图添加边
{
edge1[edgeNum1].to = b;
edge1[edgeNum1].next = adj1[a];
edge1[edgeNum1].value = len;
adj1[a] = edgeNum1++;
}

int main()
{
int a, b, len, i, s, t, k;
while(scanf("%d %d", &N, &M)!=EOF)
{
for(i=0; i<N; i++)
{
adj[i] = -1;
adj1[i] = -1;
}
for(edgeNum=i=0; i<M; i++)
{
scanf("%d %d %d", &a, &b, &len);
addEdge1(a-1, b-1, len); //构造原图
addEdge(b-1, a-1, len); //构造反向图
}
scanf("%d %d %d", &s, &t, &k);
Dijkstra(t-1); //求原图中各点到终点的最短路
int ans = A_star(s-1, t-1, k); //求第k短路
printf("%d\n", ans);
}
return 0;
}

SPFA

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
#define INF 0x3f3f3f
#define maxn 1010
typedef pair<int, int> pii;
struct edge{int to, cost;};
vector<edge> G[maxn];//正向图,邻接表
vector<edge> rG[maxn];//反向图,邻接表
int s, t, k;
int n, m, ok;

int d[maxn], In_que[maxn];//反向spfa
void spfa(int s){
memset(In_que, 0, sizeof(In_que));
memset(d, INF, sizeof(d));
queue<int> Q;
Q.push(s);
d[s] = 0;
In_que[s] = 1;
while (!Q.empty()){
int u = Q.front();
Q.pop();
In_que[u] = 0;
for (int i = 0; i < rG[u].size(); i++){
edge e = rG[u][i];
int v = e.to, dd = d[u] + e.cost;
if (d[v] > dd){
d[v] = dd;
if (!In_que[v]){
Q.push(v);
In_que[v] = 1;
}
}
}
}
}

struct state{
int u, g, h;
bool operator < (const state &b) const{
return g + h > b.g + b.h;
}
state(int a, int b, int c):u(a), g(b), h(c){}
};
int cnt[maxn], kd[maxn];
void Astar(){
memset(cnt, 0, sizeof(cnt));
priority_queue<state> Q;//open表
Q.push(state(s, 0, d[s]));
while (!Q.empty()){
state cur = Q.top();
Q.pop();
int u = cur.u;
cnt[u]++;
if (cnt[u] == k && u == t){//终点第k次出队
printf("%d\n", cur.g);
ok = 1;
break;
}
if (cnt[u] > k)//如果出队次数大于k,不用拓展了,因为一个点的第k短距离肯定是由周围点的
//前k短距离更新得来
continue;
for (int i = 0; i < G[u].size(); i++){
edge e = G[u][i];
if (cnt[e.to] != k){//如果这个点不在closed表中
Q.push(state(e.to, cur.g + e.cost, d[e.to]));
}
}
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++){
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
G[u].push_back((edge){v, c});
rG[v].push_back((edge){u, c});//反向建边
}
scanf("%d%d%d", &s, &t, &k);
if (s == t) k++;//题目特殊要求。。
spfa(t);
Astar();
if (!ok)//如果没有第k短路
printf("-1\n");
return 0;
}

生成树

瓶颈生成树

每次询问(u,v)(u, v)(u,v),在这两个点间找一条路径使得这个路径上最大的边权最小

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
#define N 50010
#define M 100010
struct Edge {
int from, to, dis, nex;
}edge[M<<1], hehe[M<<1];
bool cmp(Edge a, Edge b){return a.dis < b.dis;}
int head[N], edgenum;
void add(int u, int v, int d){
Edge E = {u,v,d,head[u]};
edge[edgenum] = E;
head[u] = edgenum++;
}
int f[N];
int find(int x){return x==f[x] ? x : f[x] = find(f[x]);}
bool Union(int x, int y){
int fx = find(x), fy = find(y);
if(fx == fy)return false;
if(fx>fy)swap(fx,fy);
f[fx] = fy;
return true;
}
int fa[N][20], dep[N], cost[N][20]; //cost[u][i]表示u点到u的第2^i次父亲 路径上最大边权
void bfs(int root){
queue<int>q;
fa[root][0] = root; dep[root] = 0;
cost[root][0] = 0;
q.push(root);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 1; i < 20; i++) {
fa[u][i] = fa[fa[u][i-1]][i-1];
cost[u][i] = max(cost[u][i-1], cost[fa[u][i-1]][i-1]);
}
for(int i = head[u]; ~i; i = edge[i].nex) {
int v = edge[i].to; if(v == fa[u][0])continue;
dep[v] = dep[u]+1; fa[v][0] = u; cost[v][0] = edge[i].dis;
q.push(v);
}
}
}
int work(int x, int y){
int ans = 0;
if(dep[x] < dep[y]) swap(x, y);
for(int i = 0; i < 20; i++) if((dep[x]-dep[y])&(1<<i)) {
ans = max(ans, cost[x][i]);
x = fa[x][i];
}
if(x == y)return ans;
for(int i = 19; i >= 0; i--)if(fa[x][i]!=fa[y][i]) {
ans = max(ans, max(cost[x][i], cost[y][i]));
x = fa[x][i], y = fa[y][i];
}
ans = max(ans, cost[x][0]);
ans = max(ans, cost[y][0]);
return ans;
}
int main(){
int i, j, u, v, d, query, n, m, fir = 0;
while(~scanf("%d %d",&n,&m)){
if(fir++)puts("");
memset(head, -1, sizeof head); edgenum = 0;
for(i = 1; i <= n; i++) f[i] = i;
for(i = 0; i < m; i++){
read(hehe[i].from); read(hehe[i].to); read(hehe[i].dis);
}
sort(hehe, hehe + m, cmp);
int siz = 0;
for(int i = 0; i < m && siz < n; i++) {
if(Union(hehe[i].from, hehe[i].to)){
siz++;
add(hehe[i].from, hehe[i].to, hehe[i].dis);
add(hehe[i].to, hehe[i].from, hehe[i].dis);
}
}
bfs(1);
read(query);
while(query--){
read(u); read(v);
printf("%d\n", work(u, v));
}
}
return 0;
}

k小生成树

输出(∑k=1Kk⋅V(k)) mod 232(_{k=1}^{K}{k V(k)}) 2^{32}(k=1∑K​k⋅V(k))mod232(V(k)V(k)V(k)是k小生成树的权值和)

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
const int MAXN = 1000+100;
const int M = 3000;
const int MO=(1LL<<32);
int n,m,k,ca,cb;
struct node{
int v,w,nex;
}e[M*2];
int EN,head[M*2],fa[MAXN],A[100010],B[100010];
struct edge{
int u,v,w;
edge(int u,int v,int w):u(u),v(v),w(w){}
edge(){}
};
vector<edge> ve;
void init()
{
memset(head,-1,sizeof head);
EN = 0;
ve.clear();
ca=0;cb=0;
for(int i=0;i<=n;i++)fa[i]=i;
}
void add(int u,int v,int w)
{
e[EN].v=v,e[EN].w=w,e[EN].nex=head[u];
head[u]=EN++;
}
int fand(int x)
{
return fa[x]==x?x:fa[x]=fand(fa[x]);
}
bool dfs(int u,int f,int en)
{
if(u==en)return true;
for(int i=head[u];~i;i=e[i].nex)
{
if(i==f) continue;
if(dfs(e[i].v,i^1,en))
{
B[cb++]=e[i].w;
return true;
}
}
return false;
}
bool cmp(int a,int b)
{
return a>b;
}
void merg()
{
if(ca > cb) swap(ca,cb),swap(A,B);
int siz = min(k,ca*cb);
priority_queue<pair<int,int> >q;
for(int i=0;i<ca;i++) q.push(make_pair(A[i]+B[0],0));
ca=siz;
for(int i=0;i<siz;i++)
{
pair<int,int>p = q.top();q.pop();
A[i] = p.first;
if(p.second+1<cb) q.push(make_pair(p.first-B[p.second]+B[p.second+1],p.second+1));
}
}
main()
{
ios::sync_with_stdio(false);
int tt=0;
while(cin>>n>>m)
{
init();
int sum=0;
int u,v,w;
while(m--)
{
cin>>u>>v>>w;
if(fand(u)!=fand(v))
{
add(u,v,w);
add(v,u,w);
fa[fand(u)]=fand(v);
}else
{
ve.push_back(edge(u,v,w));
}
sum+=w;
}cin>>k;
for(auto E : ve)
{
cb=0;
B[cb++]=E.w;
dfs(E.u,-1,E.v);
sort(B,B+cb,cmp);
if(ca==0)
{
for(int i=0;i<cb;i++)
A[i]=B[i];
ca=cb;
}else
merg();
}
int ans=0;
for(int i=0;i<ca;i++)
{
ans+=(sum-A[i])*(i+1);
ans%=MO;
}
if(ans==0) ans=sum;
ans%=MO;
cout<<"Case #"<<++tt<<": "<<ans<<endl;
}
}

虚树

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
#define FOR(i,L,R) for(register int i=(L);i<=(R);++i)
#define REP(j,R,L) for(register int j=(R);j>=(L);--j)
int n;
struct Graph{//处理最初图,求lca
vector<int>G[N];
int cnt,xu[N],dep[N],p[N][27];
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
REP(i,log2(dep[x]),0)if(dep[x]-(1<<i)>=dep[y])x=p[x][i];
if(x==y)return y;
REP(i,log2(dep[x]),0)if(p[x][i]^p[y][i])x=p[x][i],y=p[y][i];
return p[x][0];
}
inline void ST(){
int k=log2(n);
FOR(j,1,k)FOR(i,1,n)if(~p[i][j-1])p[i][j]=p[p[i][j-1]][j-1];
}
inline void dfs(int u,int fa,int depth){
xu[u]=++cnt;
int sz=G[u].size()-1;
FOR(i,0,sz)if(G[u][i]^fa)dfs(G[u][i],p[G[u][i]][0]=u,dep[G[u][i]]=depth+1);
}
inline void init(){
memset(p,-1,sizeof(p));
scanf("%d",&n);
FOR(i,1,n-1){
int x,y;scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
}
}g;
bool cmp(int a,int b){
return g.xu[a]<g.xu[b];
}
struct Fake_Tree{//应该是这么翻译吧……
struct edge{
int to,next,w;
}a[N];//这里不用vector是因为清空很慢
int m,h[N],sig[N],flag[N];
int cnt,top,stk[N];
#define next a[p].next
#define to a[p].to
#define w a[p].w
inline void solv(){
……
FOR(i,1,m)flag[sig[i]]=0;//记得清空。。。
}
inline void add(int u,int v){
if(u==v)return ;//注意这里很重要!
a[++cnt]=(edge){v,h[u],g.dep[v]-g.dep[u]};h[u]=cnt;//因为每次维护一条树链且是单位长度,所以u和v的距离就是他们之间的深度
}
inline void init(){
scanf("%d",&m);
FOR(i,1,m)scanf("%d",sig+i);//读入key point
sort(sig+1,sig+m+1,cmp);
FOR(i,1,m)flag[sig[i]]=1;//标记
//注意有的题可以删去一些关键点
cnt=top=0;
stk[++top]=1;
FOR(i,1,m){
int now=sig[i],lca=g.lca(now,stk[top]);
while(g.dep[lca]<g.dep[stk[top-1]]){//因为是维护树链,所以可用深度判断
add(stk[top-1],stk[top]);
--top;
}add(lca,stk[top]);
stk[top]=lca;//直接覆盖,注意上面使用top-1判断
if(stk[top]!=now)stk[++top]=now;//判断稳妥一点
}while(--top)add(stk[top],stk[top+1]);//最后剩在栈里的一条链
}
}z;
int main(){
g.init(); //读入原图
g.dfs(1,g.p[1][0]=0,g.dep[1]=1);
g.ST();
int Case;scanf("%d",&Case);
while(Case--){
z.init();//读入关键点
z.solv();
}return 0;
}

欧拉回路

第一行一个整数 t,表示子任务编号。t∈{1,2},如果 t=1 则表示处理无向图的情况,如果t=2 则表示处理有向图的情况。

第二行两个整数 n,m,表示图的结点数和边数。

接下来 m 行中,第 i 行两个整数 vi,ui,表示第 i 条边(从 1 开始编号)。保证 1≤vi,ui≤n。

1.如果 t=1 则表示 vi 到 ui 有一条无向边。

2.如果 t=2 则表示 vi 到 ui 有一条有向边。

图中可能有重边也可能有自环。

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
int T,n,m,p,d[100010],ru[100010],chu[100010],ans[200010],h[100010];
vector<int> b;
struct data
{
int x,id;
data(int a=0,int b=0):x(a),id(b){}
};
vector<data> a[100010];
bool v[200010];

void dfs1(int x,int y)
{
if (a[x].size()>h[x])
{
while (v[abs(a[x][h[x]].id)])
{
h[x]++;
if (h[x]==a[x].size()) break;
}
if (a[x].size()>h[x])
{
int i=a[x][h[x]].x,j=a[x][h[x]].id;
h[x]++;v[abs(j)]=1;
if (i!=y) dfs1(i,y);
ans[++p]=j;
}
}
if (a[x].size()>h[x])
{
while (v[abs(a[x][h[x]].id)])
{
h[x]++;
if (h[x]==a[x].size()) break;
}
if (a[x].size()>h[x]) dfs1(x,x);
}
}

void dfs2(int x,int y)
{
if (a[x].size()>h[x])
{
int i=a[x][h[x]].x,j=a[x][h[x]].id;
h[x]++;
if (i!=y) dfs2(i,y);
ans[++p]=j;
}
if (a[x].size()>h[x]) dfs2(x,x);
}

int main()
{
read(T);
if (T==1)
{
read(n);read(m);
int x,y;
for (int i=1;i<=m;i++)
read(x),read(y),d[x]++,d[y]++,a[x].push_back(data(y,i)),a[y].push_back(data(x,-i));
x=0;
for (int i=1;i<=n;i++)
if (d[i]%2==1) {puts("NO");return 0;}
else if (d[i]>0) x=i;
memset(h,0,sizeof(h));
p=0;dfs1(x,x);
if (p<m) {puts("NO");return 0;}
puts("YES");
for (int i=m;i>1;i--)
print(ans[i]),putchar(' ');
if (m>0) print(ans[1]),puts("");
}
else if (T==2)
{
read(n);read(m);
int x,y;
for (int i=1;i<=m;i++)
read(x),read(y),chu[x]++,ru[y]++,a[x].push_back(data(y,i));
x=0;
for (int i=1;i<=n;i++)
if (ru[i]!=chu[i]) {puts("NO");return 0;}
else if (ru[i]>0) x=i;
memset(h,0,sizeof(h));
p=0;dfs2(x,x);
if (p<m) {puts("NO");return 0;}
puts("YES");
for (int i=m;i>1;i--)
print(ans[i]),putchar(' ');
if (m>0) print(ans[1]),puts("");
}
return 0;
}