算法竞赛模板整理

字数统计: 30.1k字   |   阅读时长: 180分

大学打ACM时总结的一些常用数据结构和字符串算法的模板代码。主要包括树状数组、线段树、树链剖分、LCA、主席树、平衡树、树分治、CDQ分治等数据结构算法，和kmp、hash、manacher、pam、SA、SAM等字符串算法。

data structure

STL

bitset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bitset<4> bs;
cout<<bs<<endl;

bitset对于二进制有位运算符，可以通过[]运算符访问元素

count() 求bitset中1的数量
size() 求bitset的大小
test(int a) 求下标a是0还是1
any() 检查是否存在1
none() 检查是否不存在1
all() 检查是否全部为1

filp(int a)翻转下标ac
filp()翻转全部
set()全部置为1
set(int a,int b=1)将位置a设置为b
reset(int a)将位置a设为0
reset()将每一位设置为0

pb-ds rbtree

不进行区间信息整合时，可用，优点是代码量少。注意常数极大。

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
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pt,null_type,less< pt >,rb_tree_tag,tree_order_statistics_node_update> rbtree;

/*
定义一颗红黑树
int 关键字类型
null_type无映射(低版本g++为null_mapped_type)
less<int>从小到大排序
rb_tree_tag 红黑树（splay_tree_tag）
tree_order_statistics_node_update结点更新
插入t.insert();
删除t.erase();
Rank:t.order_of_key();
第K值:t.find_by_order();
前驱:t.lower_bound();
后继t.upper_bound();
a.join(b)b并入a 前提是两棵树的key的取值范围不相交
a.split(v,b)key小于等于v的元素属于a，其余的属于b
T.lower_bound(x)   >=x的min的迭代器
T.upper_bound((x)  >x的min的迭代器
T.find_by_order(k) 有k个数比它小的数
*/

struct pt{
    int first,second;
    pt(int x,int y) :first(x),second(y) {}
    bool operator<(const pt h)const{
        return first<h.first || (first==h.first&&second<h.second);
    }
    bool operator==(const pt h)const{
        return first==h.first&&second==h.second;
    }
};

pb_ds priority_queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<ext/pb_ds/priority_queue.hpp>
typedef __gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag> heap;
heap::point_iterator hit[M];
heap pq;
pb_ds库的push操作是有返回值的（与STL不同），返回的类型就是迭代器，
这样用一个迭代器数组保存所有push进优先队列的元素的迭代器，就可以随时修改优先队列内部元素了。
pq.modify(hit[e[i].to],node(e[i].to,d[e[i].to]));
a.join(b);
此时优先队列b内所有元素就被合并进优先队列a中，且优先队列b被清空。
hit[i]=pq.push(i);
if(hit[i]==0){
    pq.modify(hit[i],1);
}
pq.erase(hit[i]);

rope

2018牛客多校。序列翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <ext/rope>
二叉树实现，存储字符串，时间复杂度O(logN)
using namespace __gnu_cxx;
rope<int> T;
for(int i=1;i<=n;i++) T.push_back(i);
T = T.substr(p,s) + T.substr(0,p)+T.substr(p+s,n-p-s);
for(int i=1;i<=n;i++) printf("%d ",T.at(i));
可持久化：
rope<char> *his[maxn];
his[0] = new rope<char>();
his[i] = new rope<char>(*his[i-1]);
O(1)copy历史版本
insert(位置,值)
erase(位置，大小)
substr(位置，大小)
test.push_back(x);//在末尾添加x
test.insert(pos,x);//在pos插入x　　
test.erase(pos,x);//从pos开始删除x个
test.copy(pos,len,x);//从pos开始到pos+len为止用x代替
test.replace(pos,x);//从pos开始换成x
test.substr(pos,x);//提取pos开始x个
test.at(x)/[x];//访问第x个元素

list

百度之星。合并两个链表。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
list<int> mp[300005];
int main(){
    //freopen("a.in","r",stdin);
    int t;scanf("%d",&t);
    while(t--){
        int n,q;scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            mp[i].clear();
        }
        int op,a,b;
        while(q--){
            scanf("%d",&op);
            if(op==1){
                scanf("%d%d",&a,&b);
                mp[a].push_back(b);
            }
            else if(op==2){
                scanf("%d",&a);
                if(mp[a].empty()){
                    puts("EMPTY");
                }
                else{
                    int v=mp[a].back();
                    mp[a].pop_back();
                    printf("%d\n",v);
                }
            }
            else{
                scanf("%d%d",&a,&b);
                mp[a].splice(mp[a].end(),mp[b]);
            }
        }
        for(int i=1;i<=n;i++){
            mp[i].clear();
        }
    }
    return 0;
}

nth_element

2018牛客多校第六场。$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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
unsigned n, A, B, C;
unsigned x = A, y = B, z = C;
unsigned tang(){
    unsigned t;
    x ^= x << 16;x ^= x >> 5;x ^= x << 1;t = x;x = y;y = z;z = t ^ x ^ y;
    return z;
}
ull a[10000007];
int main(){
    int T;
    scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca) {
        int l=1,r=0;
        scanf("%u%u%u%u", &n, &A, &B, &C);
        x = A, y = B, z = C;
        for(int i=1;i<=n;i++){
            a[i]=tang();
        }
        int m=min(100,(int)n);
        ull ans=0;
        nth_element(a+1,a+1+n-m,a+1+n);
        for(int i=n-m+1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                ans=max(ans,a[i]*a[j]/__gcd(a[i],a[j]));
            }
        }
        printf("Case #%d: %llu\n", ca, 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
#include <bits/stdc++.h>
using namespace std;
struct node{
    int v;
    node *l,*r;
    node():l(NULL),r(NULL){};
    node(int v):v(v),l(NULL),r(NULL){};
};
void build(node* u,int val){
    if(val < u->v){
        if(u->l!=NULL)build(u->l,val);
        else u->l = new node(val);
    }else{
        if(u->r!=NULL)build(u->r,val);
        else u->r = new node(val);
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;n--;
        int x;cin>>x;
        node* root = new node();
        root->v = x;
        while(n--){
            cin>>x;
            build(root,x);
        }
    }
    return 0;
}

指针动态开点trie

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
using namespace std;
#define ll long long
int t,n,a,ok;
char s[100];
struct trie{
    trie *child[11];
    bool qwq;
    trie(){
        qwq=false;
        memset(child,0,sizeof(child));
    }
};
trie *root,*now,*next1;
void insert(char *s){
    now=root;
    int len = strlen(s);
    for(int i=0;i<len;i++){
        if(now->qwq==true)ok=0;
        int m=s[i]-'0';
        if(now->child[m]!=NULL) now = now->child[m];
        else {
            next1 = new trie;
            now->child[m] = next1;
            now = next1;
        }
        if(i==len-1)  now->qwq=true;
    }
}
void removetrie(trie* u){
    if(u==NULL) return ;
    for(int i=0;i<10;i++)removetrie(u->child[i]);
    delete u;
}
int main(){
    cin>>t;
    while(t--){
        root = new trie;
        ok=1;
        cin>>n;
        for(int i=0;i<n;i++){
            scanf("%s",s);
            insert(s);
        }
        cout<<((ok)?"YES\n":"NO\n");
        removetrie(root);
    }
    return 0;
}

指针静态开点trie

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
int t,n,a,ok;
int cnt;
char s[100];
struct trie{
    trie *child[11];
    bool qwq;
    void init(){
        qwq=false;
        memset(child,0,sizeof(child));
    }
}p[100005];
inline trie* newtrie(){
    p[cnt].init();
    return &p[cnt++];
}
trie *root,*now,*next1;
void insert(char *s){
    now = root;
    next1 = NULL;
    int len = strlen(s);
    for(int i=0;i<len && ok;i++){
        if(now->qwq==true){ok=0;return;}
        int m=s[i]-'0';
        if(now->child[m]!=NULL)  now = now->child[m];
        else{
            next1 = newtrie();
            now->child[m] = next1;
            now = next1;
        }
        if(i==len-1)now->qwq=true;
    }
}
int main(){
    cin>>t;
    while(t--){
        cnt=0;
        root = newtrie();
        ok=1;
        cin>>n;
        for(int i=0;i<n;i++){
            scanf("%s",s);
            if(ok)insert(s);
        }
        cout<<((ok)?"YES\n":"NO\n");
    }
    return 0;
}

单调队列、单调栈

2019出题，利用单调性求出贡献区间。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod = 1e9+7;
const int maxn = 2e6+10;
int n;
int a[maxn];
int len1[maxn],len2[maxn];
int main(){
    freopen("std.in","r",stdin);
    freopen("stdn.out","w",stdout);
    int t;cin>>t;
    vector<pair<int,int> >vec;
    while(t--){
        while(vec.empty()==0)vec.pop_back();
        vec.push_back(make_pair(-1,0));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        ll ans=0;
        for(int i=1;i<=n;i++){
            while(vec.back().first>a[i])vec.pop_back();
            len1[i]=i-vec.back().second;
            vec.push_back(make_pair(a[i],i));
        }
        while(vec.empty()==0)vec.pop_back();
        vec.push_back(make_pair(-1,n+1));
        for(int i=n;i>=1;i--){
            while(vec.back().first>=a[i])vec.pop_back();
            len2[i]=vec.back().second-i;
            vec.push_back(make_pair(a[i],i));
            ans+=1ll*len1[i]*len2[i]*a[i];
            ans%=mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

树状数组

一维树状数组基础模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000060
int a[maxn],c[maxn];
int lowbit(int x){return x&(-x);}
int n;
int sum(int i){
    int s=0;
    while(i){
        s+=c[i];
        i-=lowbit(i);}
    return s;
}
void add(int i,int v){
    while(i<=n){
        c[i]+=v;
        i+=lowbit(i);
    }
}
int main(){
    int a,b;
    while(scanf("%d",&n)!=EOF,n){
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++){
            scanf("%d%d",&a,&b);
            add(a,1);add(b+1,-1);
        }
        for(int i=1;i<n;i++)
            printf("%d ",sum(i));
        printf("%d\n",sum(n));
    }
    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
#include<bits/stdc++.h>
const int maxn=1<<25;
const int p=1e7+10;
int a[maxn+1];
inline void add(int x,int v){x+=p;while(x<=maxn)a[x]+=v,x+=x&-x;}
inline int query(int x){x+=p;int ans=0;while(x)ans+=a[x],x&=x-1;return ans;}
inline int kth(int k,int rt=maxn){
    for(int i=rt;i>>=1;)
        if(a[rt-i]>=k)rt-=i;
        else k-=a[rt-i];
    return rt-p;
}
int n,opt,x;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&opt,&x);
        if(opt==1)add(x,1);
        if(opt==2)add(x,-1);
        if(opt==3)printf("%d\n",query(x-1)+1);
        if(opt==4)printf("%d\n",kth(x));
        if(opt==5)printf("%d\n",kth(query(x-1)));
        if(opt==6)printf("%d\n",kth(query(x)+1));
    }
}

树状数组离线求区间不同数字个数

2018牛客多校第一场。

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
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
#define max(a,b) ((a)>(b)?(a):(b))
const int N=200005, M=200005;
int bit[N], a[N], n, m, ihead[100005], inext[N];
struct Q {
    int l, r, id, ans;
}q[M];
bool cmp1(const Q &a, const Q &b) { return a.l==b.l?a.r<b.r:a.l<b.l; }
bool cmp2(const Q &a, const Q &b) { return a.id<b.id; }
inline int read() {
    int ret=0; char c;
    for(c=getchar(); c<'0' || c>'9'; c=getchar());
    for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0';
    return ret;
}
inline void add(int x, const int &y) { while(x<=n) bit[x]+=y, x+=lowbit(x); }
inline int sum(int x) { int ret=0; while(x>0) ret+=bit[x], x-=lowbit(x); return ret; }
int main() {
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(bit,0,sizeof bit);
        memset(ihead,0,sizeof ihead);
        memset(inext,0,sizeof inext);
        int i, maxi=0, l=1;
        for(i=1; i<=n; ++i){
            a[i]=read(), maxi=max(maxi, a[i]);
            a[i+n]=a[i];
        }
        n*=2;
        for(int i=1;i<=n;i++){
            maxi=max(maxi,a[i]);
        }
        for(i=n; i>=0; --i){
            inext[i]=ihead[a[i]], ihead[a[i]]=i;
        }
        for(i=0; i<=maxi; ++i){
            if(ihead[i]) add(ihead[i], 1);
        }
        for(i=1; i<=m; ++i){
            q[i].l=read(), q[i].r=read(), q[i].id=i;
            int tmp=q[i].r;
            q[i].r=n/2+q[i].l;
            q[i].l=tmp;
        }
        sort(q+1, q+1+m, cmp1);
        for(i=1; i<=m; ++i) {
            while(l<q[i].l) {
                if(inext[l]) add(inext[l], 1);
                ++l;
            }
            q[i].ans=sum(q[i].r)-sum(q[i].l-1);
        }
        sort(q+1, q+1+m, cmp2);
        for(i=1; i<=m; ++i) printf("%d\n", q[i].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
using namespace std;
#define maxn 2005
#define lowbit(i) ((i)&(-i))
#define r(x) scanf("%d",&x)
int op,n,x,y,k;
int c[maxn][maxn];
int sum(int x,int y){
    int s=0;
    for(int i=x;i;i-=lowbit(i)){
        for(int j=y;j;j-=lowbit(j)){
            s+=c[i][j];
        }
    }return s;
}
void add(int x,int y,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=n;j+=lowbit(j)){
            c[i][j]+=v;
        }
    }
}
char ch;
int main(){
    int x1,x2,y1,y2;
    int t,q;
    r(t);
    while(t--){
        memset(c,0,sizeof(c));
        r(n);r(q);
        for(int i=0;i<q;i++){
            cin>>ch;
            if(ch=='C'){
                r(x1);r(y1);r(x2);r(y2);
                add(x1,y1,1);
                add(x1,y2+1,1);
                add(x2+1,y1,1);
                add(x2+1,y2+1,1);
            }
            else{
                r(x1);r(y1);
                cout<<((sum(x1,y1)&1)?1:0)<<endl;
            }
        }
        cout<<endl;
    }
    return 0;
}

线段树

区间修改，区间求和模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid  int mid = (l+r)>>1
#define maxn 100555
typedef long long ll;
int n,q;
ll sum[maxn<<2],cur[maxn<<2];
void push_up(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void push_down(int l,int r,int rt){
    if(cur[rt]){
        intmid;
        cur[rt<<1]  += cur[rt];
        cur[rt<<1|1]+= cur[rt];
        sum[rt<<1]  += (mid-l+1)*cur[rt];
        sum[rt<<1|1]+= (r-mid)*cur[rt];
        cur[rt]=0;
    }
}
void build(int l,int r,int rt){
    intmid;cur[rt]=0;
    if(l==r){
        scanf("%lld",&sum[rt]);return;
    }build(lson);build(rson);push_up(rt);
}
void update(int ll,int rr,int val,int l,int r,int rt){
    intmid;
    if( ll<=l && rr>=r ){
        cur[rt]+=val;
        sum[rt]+=(r-l+1)*val;
        return ;
    }
    push_down(l,r,rt);
    if(ll<=mid)update(ll,rr,val,lson);
    if(rr>mid)update(ll,rr,val,rson);
    push_up(rt);
}
ll query(int ll,int rr,int l,int r,int rt){
    long long ret=0;
    if(ll<=l && rr>=r) return sum[rt];
    push_down(l,r,rt);
    intmid;
    if(ll<=mid) ret += query(ll,rr,lson);
    if(rr>mid) ret += query(ll,rr,rson);
    return ret;
}
int main(){
    cin>>n>>q;
    build(1,n,1);
    char s[2];
    int a,b,c;
    while(q--){
        scanf("%s%d%d",s,&a,&b);
        if(s[0]=='C'){
            scanf("%d",&c);
            update(a,b,c,1,n,1);
        }
        else printf("%lld\n",query(a,b,1,n,1));
    }
    return 0;
}

标记永久化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline int cross(int L,int R,int l,int r){
    L=max(L,l);R=min(R,r);return max(0,R-L+1);
}
void add(int L,int R,int l,int r,int rt){
    c[rt]+=cross(L,R,l,r);
    if(L<=l&&R>=r){
        cur[rt]++;return;
    }
    int mid = l+r>>1;
    if(!ls[rt])ls[rt]=++tot;
    if(!rs[rt])rs[rt]=++tot;
    if(L<=mid)add(L,R,l,mid,ls[rt]);
    if(R>mid) add(L,R,mid+1,r,rs[rt]);
}
ll ask(int L,int R,int l,int r,int rt,ll ad){
    if(L<=l&&R>=r)return c[rt] + ad*(r-l+1);
    int mid = l+r>>1;ll ret=0;
    if(L<=mid)ret+=ask(L,R,l,mid,ls[rt],ad + cur[rt]);
    if(R>mid) ret+=ask(L,R,mid+1,r,rs[rt],ad + cur[rt]);
    return ret;
}

and or max

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int n,m;
int a[maxn];
const int INF = (1<<20)-1;
int maxv[maxn<<2],And[maxn<<2],Or[maxn<<2];/*区间最大值，与标记，或标记*/
int Andv[maxn<<2],orv[maxn<<2];/*区间与值，区间或值*/
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void push_up(int rt){
    Andv[rt]=Andv[rt<<1]&Andv[rt<<1|1];
    orv[rt]=orv[rt<<1]|orv[rt<<1|1];
    maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
}
void work_And(int rt,int v){
    maxv[rt]&=v;And[rt]&=v;Or[rt]&=v;
    Andv[rt]&=v;orv[rt]&=v;
}
void work_or(int rt,int v){
    maxv[rt]|=v;And[rt]|=v;Or[rt]|=v;
    Andv[rt]|=v;orv[rt]|=v;
}
void push_down(int rt){
    if(And[rt]!=INF){
        work_And(rt<<1,And[rt]);
        work_And(rt<<1|1,And[rt]);
        And[rt]=INF;
    }
    if(Or[rt]){
        work_or(rt<<1,Or[rt]);
        work_or(rt<<1|1,Or[rt]);
        Or[rt]=0;
    }
}
void build(int l,int r,int rt){
    And[rt]=INF,Or[rt]=0;
    if(l==r){
        maxv[rt]=Andv[rt]=orv[rt]=a[l];return;
    }int mid = l+r>>1;
    build(lson);build(rson);
    push_up(rt);
}
void update(int L,int R,int v,int op,int l,int r,int rt){
    if(L<=l&&R>=r){
        if(op==1){
            if(((v^INF)&((orv[rt]^INF)|Andv[rt]))==(v^INF)){
                work_And(rt,v);return;
            }
        }
        else{
            if((v&((orv[rt]^INF)|Andv[rt]))==v){
                work_or(rt,v);return;
            }
        }
    }
    push_down(rt);
    int mid = l+r>>1;
    if(L<=mid)update(L,R,v,op,lson);
    if(R>mid) update(L,R,v,op,rson);
    push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r)return maxv[rt];
    push_down(rt);
    int mid = l+r>>1,ret=0;
    if(L<=mid)ret=max(ret,query(L,R,lson));
    if(R>mid) ret=max(ret,query(L,R,rson));
    return ret;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    build(1,n,1);
    int l,r,x,op;
    while(m--){
        scanf("%d%d%d",&op,&l,&r);
        if(op==3)printf("%d\n",query(l,r,1,n,1));
        else{
            scanf("%d",&x);
            update(l,r,x,op,1,n,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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn = 1e4+10;
int sum[maxn][maxn<<2];
char op[10];
int h;
double a,l;
int h1,h2;
double a1,a2;
void push_up(int rtx,int rty){
    sum[rtx][rty]=max(sum[rtx][rty<<1],sum[rtx][rty<<1|1]);
}
void buildy(int rtx,int l,int r,int rty){
    sum[rtx][rty]=-1;
    if(l==r)return;
    int mid=l+r>>1;
    buildy(rtx,l,mid,rty<<1);buildy(rtx,mid+1,r,rty<<1|1);
}
void build(int l,int r,int rtx){
    buildy(rtx,0,1000,1);
    int mid=l+r>>1;
    if(l!=r){
        build(l,mid,rtx<<1);build(mid+1,r,rtx<<1|1);
    }
}
void updatey(int rtx,int p,int v,int l,int r,int rty){
    if(l==r){
        sum[rtx][rty]=max(sum[rtx][rty],v);
        return;
    }
    int mid=l+r>>1;
    if(p<=mid)updatey(rtx,p,v,l,mid,rty<<1);
    else      updatey(rtx,p,v,mid+1,r,rty<<1|1);
    push_up(rtx,rty);
}
void update(int x,int y,int v,int l,int r,int rtx){
    updatey(rtx,y,v,0,1000,1);
    if(l!=r){
        int mid=l+r>>1;
        if(x<=mid)update(x,y,v,l,mid,rtx<<1);
        else      update(x,y,v,mid+1,r,rtx<<1|1);
    }
}
int queryy(int rtx,int L,int R,int l,int r,int rty){
    if(L<=l&&R>=r){
            return sum[rtx][rty];
    }
    int mid=l+r>>1;
    int res=-1;
    if(L<=mid)res=max(res,queryy(rtx,L,R,l,mid,rty<<1));
    if(R>mid)res=max(res,queryy(rtx,L,R,mid+1,r,rty<<1|1));
    return res;
}
int query(int Lx,int Rx,int Ly,int Ry,int l,int r,int rtx){
    if(Lx<=l&&Rx>=r)return queryy(rtx,Ly,Ry,0,1000,1);
    int mid=l+r>>1;
    int res=-1;
    if(Lx<=mid)res=max(res,query(Lx,Rx,Ly,Ry,l,mid,rtx<<1));
    if(Rx>mid)res=max(res,query(Lx,Rx,Ly,Ry,mid+1,r,rtx<<1|1));
    return res;
}
int main(){
    int m;
    while(scanf("%d",&m)!=EOF,m){
        while(m--){
            build(100,200,1);
            scanf("%s",op);
            if(op[0]=='I'){
                scanf("%d%lf%lf",&h,&a,&l);
                update(h,a*10,l*10,100,200,1);
            }
            else{
                scanf("%d%d%lf%lf",&h1,&h2,&a1,&a2);
                if(h1>h2)swap(h1,h2);
                if(a1>a2)swap(a1,a2);
                int ans=query(h1,h2,a1*10,a2*10,100,200,1);
                if(ans==-1)puts("-1");
                else printf("%.1f\n",0.1*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
// luogu-judger-enable-o2
/******权值线段树模板******/
/**
权值线段树维护全局值域信息，每个结点记录值域的值出现次数
如果值域太大，需要离线操作
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =  1e5+10;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid int mid = (l+r)>>1

ll t[maxn*4+1];
ll dt[maxn],tot;
ll hs(int x){return lower_bound(dt+1,dt+1+tot,x)-dt;}

void update(int p,int v,int l,int r,int rt){
    //单点修改 所到的值域都需要修改 复杂度logn
    t[rt]+=v;
    if(l==r)return ;
    intmid;
    if(p<=mid)update(p,v,lson);
    else update(p,v,rson);
}

int kth(int k,int l,int r,int rt){
    //如果左边多于k个，那么去左边找，否则找到右边
    if(l==r)return l;
    intmid;
    if(t[rt<<1]>=k)return kth(k,lson);
    return kth(k-t[rt<<1],rson);
}

int Rank(int p,int l,int r,int rt){
    //查询小于p的数出现的总次数，即区间[1,p-1]的数字个数，即rank
    if(l==r)return 1;
    intmid;
    if(p<=mid)return Rank(p,lson);
    return t[rt<<1]+Rank(p,rson);
}
struct node{
    ll first,second;
}p[maxn];
signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&p[i].first,&p[i].second);
        if(p[i].first!=4)dt[++tot]=p[i].second;
    }
    sort(dt+1,dt+1+tot);
    tot=unique(dt+1,dt+1+tot)-dt-1;
    for(int i=1;i<=n;i++){
        if(p[i].first==1)update(hs(p[i].second),1,1,tot,1);
        else if(p[i].first==2)update(hs(p[i].second),-1,1,tot,1);
        else if(p[i].first==3)printf("%lld\n",Rank(hs(p[i].second),1,tot,1));
        else if(p[i].first==4)printf("%lld\n",dt[kth(p[i].second,1,tot,1)]);
        else if(p[i].first==5)printf("%lld\n",dt[kth(Rank(hs(p[i].second),1,tot,1)-1,1,tot,1)] );
        else if(p[i].first==6)printf("%lld\n",dt[kth(Rank(hs(p[i].second)+1,1,tot,1),1,tot,1)]);
    }
    return 0;
}

动态开点线段树

2019山东省赛。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n;
pair<int,int> p[maxn];
bool cmp(pair<int,int >a,pair<int,int> b){
    if(a.second==b.second)return a.first<b.first;
    return a.second<b.second;
}
struct node{
    int l,r,v,ls,rs;
    node(int l=0,int r=0,int v=0,int ls=0,int rs=0):l(l),r(r),v(v),ls(ls),rs(rs){}
}seg[maxn<<2];
int cnt,ans;
int f;
void solve(int L,int R,int rt){
    if(L<=seg[rt].l && R>=seg[rt].r){
        if(seg[rt].r-seg[rt].l==0){seg[rt].v=1;f=1;ans++;return;}
        if(!seg[rt].ls){
            seg[rt].ls=++cnt;
            seg[cnt]=node(seg[rt].l,seg[rt].l+seg[rt].r>>1);
        }
        if(seg[seg[rt].ls].r - seg[seg[rt].ls].l + 1 > seg[seg[rt].ls].v)solve(L,R,seg[rt].ls);
        else{
            if(!seg[rt].rs){
                seg[rt].rs=++cnt;
                seg[cnt]=node((seg[rt].l+seg[rt].r)/2+1,seg[rt].r);
            }
            if(seg[seg[rt].rs].r - seg[seg[rt].rs].l + 1 > seg[seg[rt].rs].v)solve(L,R,seg[rt].rs);
        }
        seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;
        return;
    }
    seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;if(f)return;
    if(L<=(seg[rt].l+seg[rt].r)/2){
        if(!seg[rt].ls){
            seg[rt].ls=++cnt;
            seg[cnt]=node(seg[rt].l,seg[rt].l+seg[rt].r>>1);
        }
        if(seg[seg[rt].ls].r - seg[seg[rt].ls].l + 1 > seg[seg[rt].ls].v){
            solve(L,R,seg[rt].ls);
            seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;
            if(f)return;
        }
    }
    if(R>(seg[rt].l+seg[rt].r)/2){
        if(!seg[rt].rs){
            seg[rt].rs=++cnt;
            seg[cnt]=node((seg[rt].l+seg[rt].r)/2+1,seg[rt].r);
        }
        if(seg[seg[rt].rs].r - seg[seg[rt].rs].l + 1 > seg[seg[rt].rs].v)solve(L,R,seg[rt].rs);
    }
    seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;
}
int main(){
    int t;cin>>t;
    while(t--){
        seg[1]=node(1,1e9);
        cnt=1;ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d%d",&p[i].first,&p[i].second);
        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++){
            f=0;solve(p[i].first,p[i].second,1);
        }
        cout<<ans<<endl;
    }
    return 0;
}

势能线段树模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn = 1e6+10;
int n,m;
ll sum[maxn<<2],maxv[maxn<<2],maxv2[maxn<<2],maxcnt[maxn<<2];
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
    if(maxv[rt<<1] > maxv[rt<<1|1]){
        maxv2[rt]=max(maxv[rt<<1|1],maxv2[rt<<1]);
        maxcnt[rt]=maxcnt[rt<<1];
    }
    else if(maxv[rt<<1] == maxv[rt<<1|1]){
        maxv2[rt]=max(maxv2[rt<<1],maxv2[rt<<1|1]);
        maxcnt[rt]=maxcnt[rt<<1]+maxcnt[rt<<1|1];
    }
    else{
        maxv2[rt]=max(maxv[rt<<1],maxv2[rt<<1|1]);
        maxcnt[rt]=maxcnt[rt<<1|1];
    }
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%lld",sum+rt);
        maxv[rt]=sum[rt];maxv2[rt]=-1;maxcnt[rt]=1;return;
    }int mid=l+r>>1;
    build(lson);build(rson);push_up(rt);
}
void push_tag(int rt,int v){
    if(v>=maxv[rt])return;
    sum[rt]-=maxcnt[rt]*(maxv[rt]-v);maxv[rt]=v;
}
void push_down(int rt){
    push_tag(rt<<1,maxv[rt]);push_tag(rt<<1|1,maxv[rt]);
}
void update(int L,int R,int v,int l,int r,int rt){
    if(maxv[rt]<=v)return;
    int mid=l+r>>1;
    if(L<=l&&R>=r&&maxv2[rt]<v){
        push_tag(rt,v);
        return;
    }
    push_down(rt);
    if(L<=mid)update(L,R,v,lson);
    if(R>mid)update(L,R,v,rson);
    push_up(rt);
}
ll querysum(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return sum[rt];
    }ll ret=0,mid=l+r>>1;
    push_down(rt);
    if(L<=mid)ret+=querysum(L,R,lson);
    if(R>mid) ret+=querysum(L,R,rson);return ret;
}
ll querymax(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return maxv[rt];
    }ll ret=0,mid=l+r>>1;
    push_down(rt);
    if(L<=mid)ret=max(ret,querymax(L,R,lson));
    if(R>mid) ret=max(ret,querymax(L,R,rson));return ret;
}
int main(){
    int T;cin>>T;
    int tp,x,y,t;
    while(T--){
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while(m--){
            scanf("%d%d%d",&tp,&x,&y);
            if(tp==0){
                scanf("%d",&t);update(x,y,t,1,n,1);
            }
            else if(tp==2)printf("%lld\n",querysum(x,y,1,n,1));
            else printf("%lld\n",querymax(x,y,1,n,1));
        }
    }
    return 0;
}

线段合并问题

//pku campus, unsolved

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid int mid=l+r>>1
int lv[maxn<<2],rv[maxn<<2],mv[maxn<<2];
int n;
int a[maxn];
int last[maxn];
void push_up(int l,int r,int rt){
    intmid;
    if(lv[rt<<1]==mid-l+1)lv[rt]=lv[rt<<1]+lv[rt<<1|1];
    else lv[rt]=lv[rt<<1];
    if(rv[rt<<1|1]==r-mid)rv[rt]=rv[rt<<1|1]+rv[rt<<1];
    else rv[rt]=rv[rt<<1|1];
    mv[rt]=max(mv[rt<<1],mv[rt<<1|1]);
    mv[rt]=max(mv[rt],rv[rt<<1]+lv[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(!lv[rt]&&!rv[rt]&&!mv[rt])return;
    if(l==r){
        lv[rt]=rv[rt]=mv[rt]=0;return;
    }intmid;
    build(lson);build(rson);push_up(l,r,rt);
}
void update(int p,int v,int l,int r,int rt){
    if(p<1||p>n)return;
    if(l==r){
        lv[rt]=rv[rt]=mv[rt]=v;return;
    }intmid;
    if(p<=mid)update(p,v,lson);
    else update(p,v,rson);
    push_up(l,r,rt);
}
int main(){
    int T;read(T);
    while(T--){
        read(n);
        for(int i=0;i<=n;i++)last[i]=0;
        build(1,n,1);
        int posl=1;
        int ans=0;
        for(int i=1;i<=n;i++){
            read(a[i]);
            if(ans==n)continue;
            if(last[a[i]]>=posl){
                while(last[a[i]]>=posl){
                    update(a[posl],0,1,n,1);posl++;
                }
            }
            update(a[i],1,1,n,1);
            last[a[i]]=i;
            ans=max(ans,mv[1]);
        }
        print(ans,'\n');
    }
    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
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid int mid=(l+r)>>1
typedef long long ll;
struct seg{
    int v;
    double l,r,h;
    seg(){}
    seg(int v,double l,double r,double h):v(v),l(l),r(r),h(h){}
    friend bool operator < (seg a,seg b){
        return a.h<b.h;
    }
}s[maxn];
int n;
int cnt[maxn<<2];
double x[maxn];
double one[maxn<<2],two[maxn<<2];
void push_up(int l,int r,int rt){
    if(cnt[rt]>=2)
        two[rt]=one[rt]=x[r+1]-x[l];//覆盖2次以上，直接算长度
    else if(cnt[rt]){
        one[rt]=x[r+1]-x[l];//覆盖1次以上，直接算长度
        if(l==r)two[rt]=0;
        else two[rt]=one[rt<<1]+one[rt<<1|1];//计算子区间的1次，加上这一次
    }
    else{
        one[rt]=one[rt<<1]+one[rt<<1|1];
        two[rt]=two[rt<<1]+two[rt<<1|1];
    }
}
void update(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){
        cnt[rt]+=v;push_up(l,r,rt);
        return;
    }
    intmid;
    if(L<=mid)update(L,R,v,lson);
    if(R>mid)update(L,R,v,rson);
    push_up(l,r,rt);
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        memset(cnt,0,sizeof(cnt));
        memset(one,0,sizeof(one));
        memset(two,0,sizeof(two));
        double x1,y1,x2,y2;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            x[i]=x1;x[i+n]=x2;
            s[i]=seg(1,x1,x2,y1);
            s[i+n]=seg(-1,x1,x2,y2);
        }
        n<<=1;
        sort(x+1,x+1+n);
        sort(s+1,s+1+n);
        int len=unique(x+1,x+1+n)-(x+1);
        double ans=0;
        for(int i=1;i<n;i++)//数字代表点改为数字代表边，那么r值-1，即左闭右开
        {
            int l=lower_bound(x+1,x+1+len,s[i].l)-x;
            int r=lower_bound(x+1,x+1+len,s[i].r)-x;
            update(l,r-1,s[i].v,1,len,1);
            ans+=two[1]*(s[i+1].h-s[i].h);
        }
        printf("%.2f\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
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
using namespace std;
typedef long long LL;
const int N = 500010;
const int INF = 1e8;
struct line//线段树节点
{
    int l, r;//左右端点
    int lp, rp;//判断左右端点是否存在，存在为1，不存在未0
    int cnt, len;//cnt代表是否被覆盖，0代表未被完全覆盖，1代表被完全覆盖
    int num;//记录区间内的线段数目
}tree[4*N];
struct node//保存线段
{
    int l, r, h;
    int f;
    bool operator < (const struct node & tmp) const{
        return h < tmp.h;
    }
}seg[4*N];
int x[N];
void build(int i, int l, int r){
    tree[i].l = l;tree[i].r = r;
    tree[i].len = tree[i].cnt = tree[i].num = 0;
    tree[i].lp = tree[i].rp = 0;
    if(l == r) return;
    int mid = (l+r) >> 1;
    build(i*2, l, mid);build(i*2+1, mid+1, r);
}
int binsearch(int key, int k){
    int high = k;
    int low = 1;
    while(high >= low) {
        int mid = (high+low) >> 1;
        if(x[mid] == key)return mid;
        else if(x[mid] < key) low = mid+1;
        else high = mid-1;
    }
    return -1;
}
void maintain(int i){
    if(tree[i].cnt){
        tree[i].len = x[tree[i].r+1]-x[tree[i].l];
        tree[i].lp = tree[i].rp = tree[i].num = 1;
        return;
    }
    if(tree[i].l == tree[i].r){
        tree[i].len = tree[i].lp = tree[i].rp = tree[i].num = 0;
        return;
    }
    tree[i].len = tree[i*2].len+tree[i*2+1].len;
    tree[i].lp = tree[i*2].lp;
    tree[i].rp = tree[i*2+1].rp;
    tree[i].num = (tree[i*2].num+tree[i*2+1].num-(tree[i*2].rp&&tree[i*2+1].lp));
}
void update(int i, int l, int r, int f){
    if(tree[i].l == l && tree[i].r == r){
        tree[i].cnt += f;
        maintain(i);
        return;
    }
    int mid = (tree[i].l+tree[i].r) >> 1;
    if(mid >= r)
        update(i*2, l, r, f);
    else if(mid < l)
        update(i*2+1, l, r, f);
    else{
        update(i*2, l, mid, f);
        update(i*2+1, mid+1, r, f);
    }
    maintain(i);
}
int main(){
   // freopen("in.txt", "r", stdin);
    int n, x1, y1, x2, y2;
    while(~scanf("%d", &n)){
        int num = 1;
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            seg[num] = (struct node){x1, x2, y1, 1};
            x[num++] = x1;
            seg[num] = (struct node){x1, x2, y2, -1};
            x[num++] = x2;
        }
        sort(seg+1, seg+num);
        sort(x+1, x+num);
        int k = 1;
        for(int i = 2; i < num; i++){
            if(x[i-1] != x[i]) x[++k] = x[i];
        }
        build(1, 1, k);
        int ans = 0;
        int pre = 0;
        for(int i = 1; i < num; i++){
            int l = binsearch(seg[i].l, k);
            int r = binsearch(seg[i].r, k)-1;
            update(1, l, r, seg[i].f);
            int t = abs(tree[1].len-pre);
            pre = tree[1].len;
            ans += t;
            if(i < num-1) ans += (seg[i+1].h-seg[i].h)*2*tree[1].num;
        }
        printf("%d\n", ans);
    }
    return 0;
}

LCA

rmq版本的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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5e5+10;
int rmq[maxn<<1];
struct ST{
    int mm[maxn<<1];
    int dp[maxn<<1][20];
    void init(int n){
        mm[0]=-1;
        for(int i=1;i<=n;i++){
            mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];dp[i][0]=i;
        }
        for(int j=1;j<=mm[n];j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                dp[i][j]=rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?
                dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
            }
        }
    }
    int query(int a,int b){
        if(a>b)swap(a,b);
        int k=mm[b-a+1];
        return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?
        dp[a][k]:dp[b-(1<<k)+1][k];
    }
}st;
int F[maxn<<1],p[maxn];
int cnt;
struct edge{int to,nxt;};
edge e[maxn<<1];
int tot,head[maxn];
void adde(int u,int v){
    e[tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot++;
}
void dfs(int u,int pre,int dep){
    F[++cnt]=u;
    rmq[cnt]=dep;
    p[u]=cnt;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs(v,u,dep+1);
        F[++cnt]=u;
        rmq[cnt]=dep;
    }
}
void lca_init(int rt,int num){
    dfs(rt,rt,0);
    st.init(2*num-1);
}
int query_lca(int u,int v){return F[st.query(p[u],p[v])];}

int main(){
    memset(head,-1,sizeof head);
    int n,m,s;scanf("%d%d%d",&n,&m,&s);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        adde(u,v);adde(v,u);
    }
    lca_init(s,n);
    while(m--){
        scanf("%d%d",&u,&v);
        printf("%d\n",query_lca(u,v));
    }
    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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e4+10;
int n,q;

/*********************LCA*********************/
int dis[maxn];
int cnt;
struct edge{int to,nxt,v;};
edge e[maxn<<1];
int tot,head[maxn];
void adde(int u,int v,int w){
    e[tot].to=v;
    e[tot].v=w;
    e[tot].nxt=head[u];
    head[u]=tot++;
}
int fa[maxn][16];
int dep[maxn];
void bfs(int rt){
    queue<int> q;
    dep[rt]=0;
    fa[rt][0]=rt;
    q.push(rt);
    while(!q.empty()){
        int tmp=q.front();q.pop();
        for(int i=1;i<16;i++)
            fa[tmp][i]=fa[fa[tmp][i-1]][i-1];
        for(int i=head[tmp];i!=-1;i=e[i].nxt){
            int v=e[i].to;
            if(v==fa[tmp][0])continue;
            dep[v]=dep[tmp]+1;
            dis[v]=dis[tmp]+e[i].v;
            fa[v][0]=tmp;
            q.push(v);
        }
    }
}
int query_lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    int hu=dep[u],hv=dep[v];
    int tu=u,tv=v;
    for(int det=hv-hu,i=0;det;det>>=1,i++)
        if(det&1)tv=fa[tv][i];
    if(tu==tv)return tu;
    for(int i=15;i>=0;i--){
        if(fa[tu][i]==fa[tv][i])continue;
        tu=fa[tu][i];tv=fa[tv][i];
    }return fa[tu][0];
}
int query_kth(int u,int k){
    for(int det=k,i=0;det;det>>=1,i++)if(det&1)u=fa[u][i];return u;
}
/*********************LCA*********************/

int main(){
    int u,v,w;
    char op[10];
    int t;cin>>t;
    while(t--){
        memset(head,-1,sizeof head);tot=0;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            adde(u,v,w);adde(v,u,w);
        }bfs(1);
        while(scanf("%s",op)!=EOF&&op[1]!='O'){
            if(op[1]=='I'){
                scanf("%d%d",&u,&v);
                printf("%d\n",dis[u]+dis[v]-2*dis[query_lca(u,v)]);
            }
            else{
                scanf("%d%d%d",&u,&v,&w);
                int fa=query_lca(u,v);
                if(dep[u]-dep[fa]+1>=w){
                    printf("%d\n",query_kth(u,w-1));
                }
                else{
                    printf("%d\n",query_kth(v,dep[v]-dep[fa]+1-(w-(dep[u]-dep[fa]))));
                }
            }
        }puts("");
    }
    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
struct edge{int nxt,to,v;}e[maxn<<1];
int cnt,head[maxn];
int fa[maxn],deep[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],id[maxn];
int dis[maxn];
void adde(int u,int v,int w){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].v=w;
    head[u]=cnt;
}
void dfs1(int u,int pre,int dep){
    fa[u]=pre;deep[u]=dep;siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dis[v]=dis[u]+e[i].v;
        dfs1(v,u,dep+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;id[u]=++cnt;rk[cnt]=u;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])dfs2(v,v);
    }
}
int query_lca(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        x=fa[top[x]];
    }return deep[x]<deep[y]?x:y;
}

树链剖分

点权模板

luogu qtree3。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn = 1e5+10;
int n,q;
struct edge{int nxt,to;}e[maxn<<1];
int cnt,head[maxn];
int fa[maxn],deep[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],id[maxn];
void adde(int u,int v){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void dfs1(int u,int pre,int dep){
    fa[u]=pre;deep[u]=dep;siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs1(v,u,dep+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;id[u]=++cnt;rk[cnt]=u;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])dfs2(v,v);
    }
}
/***************************/
int sum[maxn<<2];
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        sum[rt]^=1;
        return;
    }
    int mid=l+r>>1;
    if(L<=mid)update(L,R,lson);
    if(R>mid) update(L,R,rson);
    push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(sum[rt]==0)return 0;
    if(l==r)return l;
    int mid=l+r>>1;
    if(L<=l&&R>=r){
        if(sum[rt<<1])return query(L,R,lson);
        return query(L,R,rson);
    }
    int ret=0;
    if(L<=mid)ret=query(L,R,lson);
    if(ret)return ret;
    if(R>mid)ret=query(L,R,rson);
    return ret;
}
/***************************/
int qquery(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]] < deep[top[y]])swap(x,y);
        int tmp=query(id[top[x]],id[x],1,n,1);
        if(tmp)ans=tmp;
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    int tmp=query(id[x],id[y],1,n,1);
    if(tmp)ans=tmp;
    return ans;
}
void uupdate(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]] < deep[top[y]])swap(x,y);
        update(id[top[x]],id[x],1,n,1);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    update(id[x],id[y],1,n,1);
}
/***************************/
int u,v,w;
char op[10];

int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        adde(u,v);adde(v,u);
    }
    rk[0]=-1;
    cnt=0;dfs1(1,0,1);dfs2(1,1);
    while(q--){
        scanf("%s",op);
        if(op[0]=='0'){
            scanf("%d",&u);
            uupdate(u,u);
        }else{
            scanf("%d",&u);
            printf("%d\n",rk[qquery(1,u)]);
        }
    }
    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
struct edge{int nxt,to,v;}e[maxn<<1];
int cnt,head[maxn];
int fa[maxn],deep[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],id[maxn];
int dis[maxn];
void adde(int u,int v,int w){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].v=w;
    head[u]=cnt;
}
void dfs1(int u,int pre,int dep){
    fa[u]=pre;deep[u]=dep;siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dis[v]=dis[u]+e[i].v;
        dfs1(v,u,dep+1);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;id[u]=++cnt;rk[cnt]=u;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])dfs2(v,v);
    }
}
int qquery(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]] < deep[top[y]])swap(x,y);
        ans=max(ans , query(id[top[x]],id[x],1,n,1));
        x=fa[top[x]];
    }
    if(x==y)return ans;
    if(deep[x]>deep[y])swap(x,y);
    ans = max(ans , query(id[son[x]],id[y],1,n,1));
    return ans;
}
void uupdate(int x,int y,int v){
    while(top[x]!=top[y]){
        if(deep[top[x]] < deep[top[y]])swap(x,y);
        update(id[top[x]],id[x],v,1,n,1);
        x=fa[top[x]];
    }
    if(x==y)return;
    if(deep[x]>deep[y])swap(x,y);
    update(id[son[x]],id[y],v,1,n,1);
}

虚树 东北四省赛D

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int N=500010,M=2010,K=M*4,inf=~0U>>1;
int Case,n,m,i,o,x,y,z,root,op[M][4];
int vip[N],g[N],v[N<<1],nxt[N<<1],ed,f[N],d[N],id[N],cnt;
int at[K],G[K],W[K],NXT[K],F[K],D[K];
int vv[K],ve[K];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void addedge(int x,int y,int z){NXT[y]=G[x];G[x]=y;W[y]=z;}
inline void umin(int&a,int b){a>b?(a=b):0;}
inline void umax(int&a,int b){a<b?(a=b):0;}
inline int abs(int x){return x>0?x:-x;}
inline void swap(int&a,int&b){int c=a;a=b;b=c;}
void dfs(int x){
  int deg=0;
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==f[x])continue;
    f[u]=x;
    d[u]=d[x]+1;
    dfs(u);
    if(!id[u])continue;
    deg++;
    id[x]^=id[u];
  }
  if(deg>1)vip[x]=1;
  if(!vip[x])return;
  id[x]=++cnt;
  at[cnt]=x;
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==f[x])continue;
    u=id[u];
    if(!u)continue;
    addedge(cnt,u,d[at[u]]-d[x]-1);
  }
}
void dfs2(int x,int y){
  F[x]=y;
  D[x]=D[y]+1;
  for(int i=G[x];i;i=NXT[i])dfs2(i,x);
}
int main(){
  int size=64<<20;//64MB
  char *p=(char*)std::malloc(size)+size;
  __asm__("movl %0, %%esp\n"::"r"(p));
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(ed=cnt=i=0;i<=n;i++)f[i]=d[i]=id[i]=vip[i]=g[i]=0;
    memset(G,0,sizeof G);
    memset(W,0,sizeof W);
    memset(F,0,sizeof F);
    memset(D,0,sizeof D);
    memset(vv,0,sizeof vv);
    memset(ve,0,sizeof ve);
    for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for(i=1;i<=m;i++){
      scanf("%d%d%d",&o,&x,&y);
      vip[x]=vip[y]=1;
      op[i][0]=o;
      op[i][1]=x;
      op[i][2]=y;
      if(o==1||o==2||o==3||o==7)scanf("%d",&op[i][3]);
    }
    for(i=1;i<=n;i++)if(vip[i])root=i;
    dfs(root);
    dfs2(id[root],0);
    for(i=1;i<=m;i++){
      o=op[i][0];
      x=id[op[i][1]];
      y=id[op[i][2]];
      z=op[i][3];
      if(o==1){
        while(x!=y){
          if(D[x]<D[y])swap(x,y);
          vv[x]+=z;
          ve[x]+=z;
          x=F[x];
        }
        vv[x]+=z;
      }
      if(o==2){
        while(x!=y){
          if(D[x]<D[y])swap(x,y);
          vv[x]^=z;
          ve[x]^=z;
          x=F[x];
        }
        vv[x]^=z;
      }
      if(o==3){
        while(x!=y){
          if(D[x]<D[y])swap(x,y);
          if(vv[x]>=z)vv[x]-=z;
          if(ve[x]>=z)ve[x]-=z;
          x=F[x];
        }
        if(vv[x]>=z)vv[x]-=z;
      }
      if(o==4){
        long long ans=0;
        while(x!=y){
          if(D[x]<D[y])swap(x,y);
          ans+=vv[x];
          ans+=1LL*ve[x]*W[x];
          x=F[x];
        }
        printf("%lld\n",ans+vv[x]);
      }
      if(o==5){
        int ans=0;
        while(x!=y){
          if(D[x]<D[y])swap(x,y);
          ans^=vv[x];
          if(W[x]&1)ans^=ve[x];
          x=F[x];
        }
        printf("%d\n",ans^vv[x]);
      }
      if(o==6){
        int mi=inf,ma=0;
        while(x!=y){
          if(D[x]<D[y])swap(x,y);
          umin(mi,vv[x]);
          umax(ma,vv[x]);
          if(W[x]){
            umin(mi,ve[x]);
            umax(ma,ve[x]);
          }
          x=F[x];
        }
        umin(mi,vv[x]);
        umax(ma,vv[x]);
        printf("%d\n",ma-mi);
      }
      if(o==7){
        int ans=inf;
        while(x!=y){
          if(D[x]<D[y])swap(x,y);
          umin(ans,abs(vv[x]-z));
          if(W[x])umin(ans,abs(ve[x]-z));
          x=F[x];
        }
        umin(ans,abs(vv[x]-z));
        printf("%d\n",ans);
      }
    }
  }
}

主席树

省内存

1
2
3
4
5
6
7
8
void update(int &u,int p,int l,int r){
    ++tot;lson[tot]=lson[u];rson[tot]=rson[u];c[tot]=c[u]+1;
    u=tot;
    if(l==r)return;
    int mid=l+r>>1;
    if(p<=mid)update(lson[u],p,l,mid);
    else      update(rson[u],p,mid+1,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
const int maxn = 2e6+10;
int n,q,m,tot;
int a[maxn],t[maxn];
int T[maxn],lson[maxn*22],rson[maxn*22],c[maxn*22];
void init_hs(){
    for(int i=1;i<=n;i++){
        t[i]=a[i];
    }sort(t+1,t+1+n);
    m = unique(t+1,t+1+n)-t-1;
}
int build(int l,int r){
    int root=tot++;
    c[root]=0;
    if(l!=r){
        int mid=l+r>>1;
        lson[root]=build(l,mid);
        rson[root]=build(mid+1,r);
    }
    return root;
}
int hs(int x){return lower_bound(t+1,t+1+m,x)-t;}
int update(int root,int pos,int val){
    int newroot=tot++,tmp=newroot;
    c[newroot]=val;
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(pos<=mid){
            lson[newroot]=tot++;
            rson[newroot]=rson[root];
            newroot=lson[newroot];
            root=lson[root];
            r=mid;
        }
        else{
            rson[newroot]=tot++;
            lson[newroot]=lson[root];
            newroot=rson[newroot];
            root=rson[root];
            l=mid+1;
        }
        c[newroot]=val;
    }
    return tmp;
}
int query(int root,int id){
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(id<=mid){
            r=mid;
            root=lson[root];
        }
        else{
            l=mid+1;
            root=rson[root];
        }
    }
    return c[root];
}
int v[maxn];
int main(){
    read(n,m);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    T[n+1]=build(1,n);
    for(int i=n;i;i--){
        T[i]=update(T[i+1],i,a[i]);
    }
    v[0]=T[1];
    int op,vi,loci,valuei;
    for(int i=1;i<=m;i++){
        read(vi,op);
        if(op==1){
            read(loci,valuei);
            v[i]=update(v[vi],loci,valuei);
        }
        else{
            read(loci);
            v[i]=v[vi];
            print(query(v[i],loci),"\n");
        }
    }
    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
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,q,m,tot;
int a[maxn],t[maxn];
int T[maxn*20],lson[maxn*20],rson[maxn*20],c[maxn*20];
void init_hs(){
    for(int i=1;i<=n;i++){
        t[i]=a[i];
    }
    sort(t+1,t+1+n);
    m = unique(t+1,t+1+n)-t-1;
}
int build(int l,int r){
    int root=tot++;
    c[root]=0;
    if(l!=r){
        int mid=l+r>>1;
        lson[root]=build(l,mid);
        rson[root]=build(mid+1,r);
    }
    return root;
}
int hs(int x){
    return lower_bound(t+1,t+1+m,x)-t;
}
int update(int root,int pos,int val){
    int newroot=tot++,tmp=newroot;
    c[newroot]=c[root]+val;
    int l=1,r=m;
    while(l<r){
        int mid=l+r>>1;
        if(pos<=mid){
            lson[newroot]=tot++;
            rson[newroot]=rson[root];
            newroot=lson[newroot];
            root=lson[root];
            r=mid;
        }
        else{
            rson[newroot]=tot++;
            lson[newroot]=lson[root];
            newroot=rson[newroot];
            root=rson[root];
            l=mid+1;
        }
        c[newroot]=c[root]+val;
    }
    return tmp;
}
int query(int left_root,int right_root,int k){
    int l=1,r=m;
    while(l<r){
        int mid=l+r>>1;
        if(c[lson[left_root]] - c[lson[right_root]] >= k){
            r=mid;
            left_root=lson[left_root];
            right_root=lson[right_root];
        }
        else{
            l=mid+1;
            k-=c[lson[left_root]]-c[lson[right_root]];
            left_root=rson[left_root];
            right_root=rson[right_root];
        }
    }
    return l;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    init_hs();
    T[n+1]=build(1,m);
    for(int i=n;i;i--){
        int pos = hs(a[i]);
        T[i] = update(T[i+1],pos,1);
    }
    while(q--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",t[query(T[l],T[r+1],k)]);
    }
    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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n,m;
struct node{int op,l,r,k;}q[maxn];
int a[maxn];
char op[2];
int lson[maxn<<7],rson[maxn<<7],c[maxn<<7];
int T[maxn],S[maxn],use[maxn],tot;
int cntn;
int dt[maxn];
int hs(int x){return lower_bound(dt+1,dt+1+cntn,x)-dt;}
int build(int l,int r){
    int rt=tot++;c[rt]=0;
    if(l!=r){
        int mid=l+r>>1;
        lson[rt]=build(l,mid);rson[rt]=build(mid+1,r);
    }return rt;
}
int ins(int rt,int pos,int val){
    int nrt=tot++,tmp=nrt;
    int l=1,r=cntn;
    c[nrt]=c[rt]+val;
    while(l<r){
        int mid=l+r>>1;
        if(pos<=mid){
            lson[nrt]=tot++;
            rson[nrt]=rson[rt];
            nrt=lson[nrt];
            rt=lson[rt];
            r=mid;
        }
        else{
            lson[nrt]=lson[rt];
            rson[nrt]=tot++;
            nrt=rson[nrt];
            rt=rson[rt];
            l=mid+1;
        }
        c[nrt]=c[rt]+val;
    }return tmp;
}
inline int lowbit(int x){return x&(-x);}
int sum(int x){
    int ans=0;
    while(x){
        ans+=c[lson[use[x]]];x-=lowbit(x);
    }return ans;
}
void update(int x,int pos,int val){
    while(x<=n){
        S[x]=ins(S[x],pos,val);x+=lowbit(x);
    }
}
int query(int L,int R,int k){
    int lrt=T[L-1];
    int rrt=T[R];
    int l=1,r=cntn;
    for(int i=L-1;i;i-=lowbit(i))use[i]=S[i];
    for(int i=R;i;i-=lowbit(i))use[i]=S[i];
    while(l<r){
        int mid=l+r>>1;
        int tmp=sum(R)-sum(L-1)+c[lson[rrt]]-c[lson[lrt]];
        if(tmp>=k){
            r=mid;
            for(int i=L-1;i;i-=lowbit(i))use[i]=lson[use[i]];
            for(int i=R;i;i-=lowbit(i))use[i]=lson[use[i]];
            lrt=lson[lrt];rrt=lson[rrt];
        }
        else{
            l=mid+1;k-=tmp;
            for(int i=L-1;i;i-=lowbit(i))use[i]=rson[use[i]];
            for(int i=R;i;i-=lowbit(i))use[i]=rson[use[i]];
            lrt=rson[lrt];rrt=rson[rrt];
        }
    }return l;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i),dt[++cntn]=a[i];
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]=='Q')q[i].op=0,scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        else scanf("%d%d",&q[i].l,&q[i].k),dt[++cntn]=q[i].k,q[i].op=1;
    }
    sort(dt+1,dt+1+cntn);cntn=unique(dt+1,dt+1+cntn)-dt-1;
    T[0]=build(1,cntn);
    for(int i=1;i<=n;i++)T[i]=ins(T[i-1],hs(a[i]),1),S[i]=T[0];
    for(int i=1;i<=m;i++){
        if(q[i].op){
            update(q[i].l,hs(a[q[i].l]),-1);
            update(q[i].l,hs(q[i].k),1);
            a[q[i].l]=q[i].k;
        }
        else printf("%d\n",dt[query(q[i].l,q[i].r,q[i].k)]);
    }
    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
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<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,q,cntn,TOT;
int a[maxn],dt[maxn];
int T[maxn],lson[maxn<<5],rson[maxn<<5],c[maxn<<5];
void init_hash(){
    sort(dt+1,dt+1+cntn);
    cntn=unique(dt+1,dt+1+cntn)-dt-1;
}
int hs(int x){return lower_bound(dt+1,dt+1+cntn,x)-dt;}
int build(int l,int r){
    int rt=TOT++;
    c[rt]=0;
    if(l!=r){
        int mid=l+r>>1;
        lson[rt]=build(l,mid);rson[rt]=build(mid+1,r);
    }return rt;
}
int update(int rt,int pos,int val){
    int nrt=TOT++,tmp=nrt;
    c[nrt]=c[rt]+val;
    int l=1,r=cntn;
    while(l<r){
        int mid=l+r>>1;
        if(pos<=mid){
            lson[nrt]=TOT++,rson[nrt]=rson[rt];nrt=lson[nrt];rt=lson[rt];r=mid;
        }else{
            rson[nrt]=TOT++,lson[nrt]=lson[rt];nrt=rson[nrt];rt=rson[rt];l=mid+1;
        }c[nrt]=c[rt]+val;
    }return tmp;
}
int query(int lrt,int rrt,int LCA,int k){
    int lcart=T[LCA];
    int pos=hs(a[LCA]);
    int l=1,r=cntn;
    while(l<r){
        int mid=l+r>>1;
        int tmp = c[lson[lrt]]+c[lson[rrt]]-2*c[lson[lcart]]+(pos>=l&&pos<=mid);
        if(tmp>=k){
            lrt=lson[lrt];rrt=lson[rrt];lcart=lson[lcart];r=mid;
        }else{
            k-=tmp;l=mid+1;
            lrt=rson[lrt];rrt=rson[rrt];lcart=rson[lcart];
        }
    }return l;
}
int rmq[maxn<<1];
struct ST{
    int mm[maxn<<1];
    int dp[maxn<<1][20];
    void init(int n){
        mm[0]=-1;
        for(int i=1;i<=n;i++){
            mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];dp[i][0]=i;
        }
        for(int j=1;j<=mm[n];j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                dp[i][j]=rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?
                dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
            }
        }
    }
    int query(int a,int b){
        if(a>b)swap(a,b);
        int k=mm[b-a+1];
        return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?
        dp[a][k]:dp[b-(1<<k)+1][k];
    }
}st;
int F[maxn<<1],p[maxn];
int cnt;
struct edge{int to,nxt;};
edge e[maxn<<1];
int tot,head[maxn];
void adde(int u,int v){
    e[tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot++;
}
void dfs(int u,int pre,int dep){
    F[++cnt]=u;
    rmq[cnt]=dep;
    p[u]=cnt;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs(v,u,dep+1);
        F[++cnt]=u;
        rmq[cnt]=dep;
    }
}
void lca_init(int rt,int num){
    dfs(rt,rt,0);
    st.init(2*num-1);
}
int query_lca(int u,int v){return F[st.query(p[u],p[v])];}
void dfs_build(int u,int pre){
    int pos=hs(a[u]);
    T[u]=update(T[pre],pos,1);
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs_build(v,u);
    }
}
int ls=0;
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",a+i),dt[++cntn]=a[i];
    init_hash();
    int u,v,k;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        adde(u,v);adde(v,u);
    }
    lca_init(1,n);
    T[0]=build(1,cntn);
    dfs_build(1,0);
    while(q--){
        scanf("%d%d%d",&u,&v,&k);u^=ls;
        printf("%d\n",ls=dt[query(T[u],T[v],query_lca(u,v),k)]);
    }
    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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define dlson l,mid,lson[nrt]
#define drson mid+1,r,rson[nrt]

const int maxn = 2e5+10;
int n,m;
int T[maxn],tot,lson[maxn<<5],rson[maxn<<5];
ll c[maxn<<5],cur[maxn<<5];
void push_up(int rt){
    c[rt]=c[lson[rt]]+c[rson[rt]];
}
void build(int l,int r,int &nrt){
    nrt=tot++;cur[nrt]=0;
    if(l==r){
        scanf("%lld",c+nrt);return;
    }int mid=l+r>>1;
    build(dlson);build(drson);push_up(nrt);
}
void update(int L,int R,ll val,int l,int r,int &nrt,int rt){
    nrt=tot++;
    lson[nrt]=lson[rt];
    rson[nrt]=rson[rt];
    c[nrt]=c[rt]+(R-L+1)*val;
    cur[nrt]=cur[rt];
    if(L==l&&R==r){
        cur[nrt]+=val;return;
    }
    int mid=l+r>>1;
    if(R<=mid)update(L,R,val,dlson,lson[rt]);
    else if(L>mid)update(L,R,val,drson,rson[rt]);
    else update(L,mid,val,dlson,lson[rt]),update(mid+1,R,val,drson,rson[rt]);
}
ll query(int L,int R,int l,int r,int nrt,ll add){
    if(L==l&&R==r)return c[nrt]+(R-L+1)*add;
    int mid=l+r>>1;
    if(R<=mid)return query(L,R,dlson,add+cur[nrt]);
    else if(L>mid)return query(L,R,drson,add+cur[nrt]);
    return query(L,mid,dlson,add+cur[nrt])+query(mid+1,R,drson,add+cur[nrt]);
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
    tot=0;
    build(1,n,T[0]);
    int time=0;
    char op[2];
    int l,r,d,t;
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]=='C'){
            scanf("%d%d%d",&l,&r,&d);
            update(l,r,d,1,n,T[time+1],T[time]);time++;
        }
        else if(op[0]=='Q'){
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(l,r,1,n,T[time],0));
        }
        else if(op[0]=='H'){
            scanf("%d%d%d",&l,&r,&t);
            printf("%lld\n",query(l,r,1,n,T[t],0));
        }
        else{
            scanf("%d",&t);
            tot=T[t+1];
            time=t;
        }
    }
    }
    return 0;
}

平衡树

treap

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
int tot=0,r=0;
int siz[maxn],v[maxn],num[maxn],rd[maxn],son[maxn][2];
/**subtree size,point value,point time,rand value,son**/
void push_up(int rt){
    siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+num[rt];
}
void rotate(int &rt,int d){
    int k=son[rt][d^1];
    son[rt][d^1]=son[k][d];
    son[k][d]=rt;
    push_up(rt);push_up(k);
    rt=k;
}
void ins(int &rt,int x){
    if(!rt){
        rt=++tot;
        siz[rt]=num[rt]=1;
        v[rt]=x;rd[rt]=rand();
        return;
    }
    if(v[rt]==x){
        num[rt]++;siz[rt]++;return;
    }
    int d=(x>v[rt]);
    ins(son[rt][d],x);
    if(rd[rt]<rd[son[rt][d]])rotate(rt,d^1);
    push_up(rt);
}
void del(int &rt,int x){
    if(!rt)return;
    if(x<v[rt])del(son[rt][0],x);
    else if(x>v[rt])del(son[rt][1],x);
    else{
        if(!son[rt][0]&&!son[rt][1]){
            num[rt]--;siz[rt]--;
            if(!num[rt])rt=0;
        }
        else if(son[rt][0]&&!son[rt][1]){
            rotate(rt,1);
            del(son[rt][1],x);
        }
        else if(!son[rt][0]&&son[rt][1]){
            rotate(rt,0);
            del(son[rt][0],x);
        }
        else{
            int d=(rd[son[rt][0]] >rd[son[rt][1]] );
            rotate(rt,d);
            del(son[rt][d],x);
        }
    }push_up(rt);
}
int rk(int rt,int x){
    if(!rt)return 0;
    if(v[rt]==x)return siz[son[rt][0]]+1;
    if(v[rt]<x)return siz[son[rt][0]]+num[rt]+rk(son[rt][1],x);
    return rk(son[rt][0],x);
}
int find(int rt,int x){
    if(!rt)return 0;
    if(siz[son[rt][0]]>=x)return find(son[rt][0],x);
    if(siz[son[rt][0]]+num[rt]<x)return find(son[rt][1],x-num[rt]-siz[son[rt][0]]);
    return v[rt];
}
int pre(int rt,int x){
    if(!rt)return -inf;
    if(v[rt]>=x)return pre(son[rt][0],x);
    return max(v[rt],pre(son[rt][1],x));
}
int nxt(int rt,int x){
    if(!rt)return inf;
    if(v[rt]<=x)return nxt(son[rt][1],x);
    return min(v[rt],nxt(son[rt][0],x));
}
int main(){
    int n;scanf("%d",&n);
    int op,x;
    for(int i=0;i<n;i++){
        scanf("%d%d",&op,&x);
        if(op==1)ins(r,x);
        else if(op==2)del(r,x);
        else if(op==3)printf("%d\n",rk(r,x));
        else if(op==4)printf("%d\n",find(r,x));
        else if(op==5)printf("%d\n",pre(r,x));
        else printf("%d\n",nxt(r,x));
    }
    return 0;
}

splay copy from kuangbin

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
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
/*
 * 给定一个数列a1,a2,...an
 * 进行以下6种操作
 * ADD x y D :给第x个数到第y个数加D(增加一个add进行延迟标记)
 * REVERSE x y :反转[x,y]之间的数(伸展树经典操作)
 * REVOLVE x y T:循环右移T次(先把T对长度进行取模，然后就相当于把[y-T+1,y]放在[x,y-T]前面)
 * INSERT x P:在第x个数后面插入P （经典的插入）
 * DELETE x:删除第x个数（删除操作）
 * MIN x y:查询[x,y]之间最小的数(标记)
 * CUT x y z 把区间[l,r]切断，贴到第z个元素后面
 * REMOVE 移除根结点
 *
 * 需要的操作:反转、删除、插入、查询区间最小值、成段更新、区间搬移(循环右移转化为区间搬移)
 * 需要的变量:pre,ch,key,size,add,rev,m(最小值)
 */

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define Key_value ch[ch[root][1]][0]//root的右儿子的左儿子
const int MAXN=200010;
const int INF=0x3f3f3f3f;
int pre[MAXN],ch[MAXN][2],key[MAXN],size[MAXN],add[MAXN],rev[MAXN],m[MAXN];
//父结点，儿子，结点权值，子树大小，相关标记
int root,tot1;
int s[MAXN],tot2;//内存池、内存池容量
int a[MAXN];
int n,q;

void NewNode(int &r,int father,int k)
{
    if(tot2)r=s[tot2--];
    else r=++tot1;
    ch[r][0]=ch[r][1]=0;
    pre[r]=father;
    size[r]=1;
    add[r]=rev[r]=0;
    key[r]=m[r]=k;
}
void Update_Rev(int r)
{
    if(!r)return;
    swap(ch[r][0],ch[r][1]);
    rev[r]^=1;
}
void Update_Add(int r,int ADD)
{
    if(!r)return;
    add[r]+=ADD;
    key[r]+=ADD;
    m[r]+=ADD;
}
void Push_Up(int r)
{
    size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
    m[r]=key[r];
    if(ch[r][0])m[r]=min(m[r],m[ch[r][0]]);
    if(ch[r][1])m[r]=min(m[r],m[ch[r][1]]);
}
void Push_Down(int r)
{
    if(rev[r])
    {
        Update_Rev(ch[r][0]);
        Update_Rev(ch[r][1]);
        rev[r]=0;
    }
    if(add[r])
    {
        Update_Add(ch[r][0],add[r]);
        Update_Add(ch[r][1],add[r]);
        add[r]=0;
    }
}
void Build(int &x,int l,int r,int father)
{
    if(l>r)return;
    int mid=(l+r)/2;
    NewNode(x,father,a[mid]);
    Build(ch[x][0],l,mid-1,x);
    Build(ch[x][1],mid+1,r,x);
    Push_Up(x);
}
void Init()
{
    root=tot1=tot2=0;
    ch[root][0]=ch[root][1]=size[root]=add[root]=rev[root]=pre[root]=0;
    m[root]=INF;//这个不用也可以，如果在push_up那判断了的话，否则需要
    NewNode(root,0,INF);
    NewNode(ch[root][1],root,INF);
    Build(Key_value,1,n,ch[root][1]);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
//旋转
void Rotate(int x,int kind)
{
    int y=pre[x];
    Push_Down(y);
    Push_Down(x);
    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if(pre[y])
        ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][kind]=y;
    pre[y]=x;
    Push_Up(y);
}
//Splay调整
void Splay(int r,int goal)
{
    Push_Down(r);
    while(pre[r]!=goal)
    {
        if(pre[pre[r]]==goal)
        {
            //这题有反转操作，需要先push_down,在判断左右孩子
            Push_Down(pre[r]);
            Push_Down(r);
            Rotate(r,ch[pre[r]][0]==r);
        }

        else
        {
            //这题有反转操作，需要先push_down,在判断左右孩子
            Push_Down(pre[pre[r]]);
            Push_Down(pre[r]);
            Push_Down(r);
            int y=pre[r];
            int kind=(ch[pre[y]][0]==y);
            //两个方向不同，则先左旋再右旋
            if(ch[y][kind]==r)
            {
                Rotate(r,!kind);
                Rotate(r,kind);
            }
            //两个方向相同，相同方向连续两次
            else
            {
                Rotate(y,kind);
                Rotate(r,kind);
            }
        }
    }
    Push_Up(r);
    if(goal==0)root=r;
}
int Get_Kth(int r,int k)
{
    Push_Down(r);
    int t=size[ch[r][0]]+1;
    if(t==k)return r;
    if(t>k)return Get_Kth(ch[r][0],k);
    else return Get_Kth(ch[r][1],k-t);
}
int Get_Min(int r)
{
    Push_Down(r);
    while(ch[r][0])
    {
        r=ch[r][0];
        Push_Down(r);
    }
    return r;
}
int Get_Max(int r)
{
    Push_Down(r);
    while(ch[r][1])
    {
        r=ch[r][1];
        Push_Down(r);
    }
    return r;
}
//下面是操作了
/**
得到区间[l,r]的步骤是，先将l-1结点旋转到root，再将r+1旋转到root的右儿子，那么[l,r]就是root的右儿子的左儿子。
Splay(Get_Kth(root,l),0);
Splay(Get_Kth(root,r+2),root);
*/
void CUT(int l,int r,int c)
{
    Splay(Get_Kth(root,l),0);
    Splay(Get_Kth(root,r+2),root);
    int tmp=Key_value;
    Key_value=0;
    Push_Up(ch[root][1]);
    Push_Up(root);
    Splay(Get_Kth(root,c+1),0);
    Splay(Get_Kth(root,c+2),root);
    Key_value=tmp;
    pre[Key_value]=ch[root][1];
    Push_Up(ch[root][1]);
    Push_Up(root);
}

void Remove()//移除根结点
{
    if(ch[root][0]==0)//没有左孩子
    {
        root=ch[root][1];
        pre[root]=0;
    }
    else
    {
        int m=Get_Max(ch[root][0]);
        Splay(m,root);
        ch[m][1]=ch[root][1];
        pre[ch[root][1]]=m;
        root=m;
        pre[root]=0;
        Push_Up(root);//要更新
    }
}

void ADD(int l,int r,int D)
{
    Splay(Get_Kth(root,l),0);
    Splay(Get_Kth(root,r+2),root);
    Update_Add(Key_value,D);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
void Reverse(int l,int r)
{
    Splay(Get_Kth(root,l),0);
    Splay(Get_Kth(root,r+2),root);
    Update_Rev(Key_value);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
void Revolve(int l,int r,int T)//循环右移
{
    int len=r-l+1;
    T=(T%len+len)%len;
    if(T==0)return;
    int c=r-T+1;//将区间[c,r]放在[l,c-1]前面
    Splay(Get_Kth(root,c),0);
    Splay(Get_Kth(root,r+2),root);
    int tmp=Key_value;
    Key_value=0;
    Push_Up(ch[root][1]);
    Push_Up(root);
    Splay(Get_Kth(root,l),0);
    Splay(Get_Kth(root,l+1),root);
    Key_value=tmp;
    pre[Key_value]=ch[root][1];//这个不用忘记
    Push_Up(ch[root][1]);
    Push_Up(root);
}
void Insert(int x,int P)//在第x个数后面插入P
{
    Splay(Get_Kth(root,x+1),0);
    Splay(Get_Kth(root,x+2),root);
    NewNode(Key_value,ch[root][1],P);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
void erase(int r)//回收内存
{
    if(r)
    {
        s[++tot2]=r;
        erase(ch[r][0]);
        erase(ch[r][1]);
    }
}
void Delete(int x)//删除第x个数
{
    Splay(Get_Kth(root,x),0);
    Splay(Get_Kth(root,x+2),root);
    erase(Key_value);
    pre[Key_value]=0;
    Key_value=0;
    Push_Up(ch[root][1]);
    Push_Up(root);
}
int Query_Min(int l,int r)
{
    Splay(Get_Kth(root,l),0);
    Splay(Get_Kth(root,r+2),root);
    return m[Key_value];
}

void Inorder(int r)
{
    if(!r)return;
    Push_Down(r);
    Inorder(ch[r][0]);
    if(cnt>=1&&cnt<=n)
    {
        printf("%d",key[r]);
        if(cnt<n)printf(" ");
        else printf("\n");
    }
    cnt++;
    Inorder(ch[r][1]);
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    char op[20];
    int x,y,z;
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        Init();
        scanf("%d",&q);
        while(q--)
        {
            scanf("%s",op);
            if(strcmp(op,"ADD")==0)
            {
                scanf("%d%d%d",&x,&y,&z);
                ADD(x,y,z);
            }
            else if(strcmp(op,"REVERSE")==0)
            {
                scanf("%d%d",&x,&y);
                Reverse(x,y);
            }
            else if(strcmp(op,"REVOLVE")==0)
            {
                scanf("%d%d%d",&x,&y,&z);
                Revolve(x,y,z);
            }
            else if(strcmp(op,"INSERT")==0)
            {
                scanf("%d%d",&x,&y);
                Insert(x,y);
            }
            else if(strcmp(op,"DELETE")==0)
            {
                scanf("%d",&x);
                Delete(x);
            }
            else
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",Query_Min(x,y));
            }
        }
    }
    return 0;
}

/*
 * 维修数列
 * 经典的伸展树的题目。
 * 题目首先给出一个数列，然后进行下列6种操作
 * 1:INSERT post tot c1,c2,...ctot :在当前数列的第pos个数字后插入tot个数字
 * 2:DELETE pos tot : 从当前数列的第pos个数字开始连续 删除tot个数字
 * 3:MAKE-SAME pos tot c :将当前数列的第pos个数字开始连续的tot个数字统一修改为c
 * 4:REVERSE pos tot : 翻转当前数列的第pos个数字来说的连续的tot个数字
 * 5:GET-SUM pos tot :计算当前数列的第pos个数字来说的连续的tot个数字的和并输出
 * 6：MAX-SUM ：求出当前数列中和最大的一段序列，输出最大和
 */
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define Key_value ch[ch[root][1]][0]
const int MAXN=500010;
const int INF=0x3f3f3f3f;
int pre[MAXN],ch[MAXN][2],key[MAXN],size[MAXN];
int sum[MAXN],rev[MAXN],same[MAXN];
int lx[MAXN],rx[MAXN],mx[MAXN];
int root,tot1;
int s[MAXN],tot2;
int a[MAXN];
int n,q;
//debug部分
void Treavel(int x)
{
    if(x)
    {
        Treavel(ch[x][0]);
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d key=%2d, size= %2d, sum=%2d,rev=%2d same=%2d lx=%2d rx=%2d mx=%2d\n",x,ch[x][0],ch[x][1],pre[x],key[x],size[x],sum[x],rev[x],same[x],lx[x],rx[x],mx[x]);
        Treavel(ch[x][1]);
    }
}
void debug()
{
    printf("root%d\n",root);
    Treavel(root);
}
void NewNode(int &r,int father,int k)
{
    if(tot2)r=s[tot2--];
    else r=++tot1;
    pre[r]=father;
    ch[r][0]=ch[r][1]=0;
    key[r]=k;
    sum[r]=k;
    rev[r]=same[r]=0;
    lx[r]=rx[r]=mx[r]=k;
    size[r]=1;
}
void Update_Same(int r,int v)
{
    if(!r)return;
    key[r]=v;
    sum[r]=v*size[r];
    lx[r]=rx[r]=mx[r]=max(v,v*size[r]);
    same[r]=1;
}
void Update_Rev(int r)
{
    if(!r)return;
    swap(ch[r][0],ch[r][1]);
    swap(lx[r],rx[r]);
    rev[r]^=1;//这里要注意，一定是异或1
}
void Push_Up(int r)
{
    int lson=ch[r][0],rson=ch[r][1];
    size[r]=size[lson]+size[rson]+1;
    sum[r]=sum[lson]+sum[rson]+key[r];
    lx[r]=max(lx[lson],sum[lson]+key[r]+max(0,lx[rson]));
    rx[r]=max(rx[rson],sum[rson]+key[r]+max(0,rx[lson]));
    mx[r]=max(0,rx[lson])+key[r]+max(0,lx[rson]);
    mx[r]=max(mx[r],max(mx[lson],mx[rson]));
}
void Push_Down(int r)
{
    if(same[r])
    {
        Update_Same(ch[r][0],key[r]);
        Update_Same(ch[r][1],key[r]);
        same[r]=0;
    }
    if(rev[r])
    {
        Update_Rev(ch[r][0]);
        Update_Rev(ch[r][1]);
        rev[r]=0;
    }
}
void Build(int &x,int l,int r,int father)
{
    if(l>r)return;
    int mid=(l+r)/2;
    NewNode(x,father,a[mid]);
    Build(ch[x][0],l,mid-1,x);
    Build(ch[x][1],mid+1,r,x);
    Push_Up(x);
}
void Init()
{
    root=tot1=tot2=0;
    ch[root][0]=ch[root][1]=pre[root]=size[root]=same[root]=rev[root]=sum[root]=key[root]=0;
    lx[root]=rx[root]=mx[root]=-INF;
    NewNode(root,0,-1);
    NewNode(ch[root][1],root,-1);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    Build(Key_value,0,n-1,ch[root][1]);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
void Rotate(int x,int kind)
{
    int y=pre[x];
    Push_Down(y);
    Push_Down(x);
    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if(pre[y])
        ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][kind]=y;
    pre[y]=x;
    Push_Up(y);
}
void Splay(int r,int goal)
{
    Push_Down(r);
    while(pre[r]!=goal)
    {
        if(pre[pre[r]]==goal)
        {
            Push_Down(pre[r]);
            Push_Down(r);
            Rotate(r,ch[pre[r]][0]==r);
        }
        else
        {
            Push_Down(pre[pre[r]]);
            Push_Down(pre[r]);
            Push_Down(r);
            int y=pre[r];
            int kind=ch[pre[y]][0]==y;
            if(ch[y][kind]==r)
            {
                Rotate(r,!kind);
                Rotate(r,kind);
            }
            else
            {
                Rotate(y,kind);
                Rotate(r,kind);
            }
        }
    }
    Push_Up(r);
    if(goal==0)root=r;
}
int Get_Kth(int r,int k)
{
    Push_Down(r);
    int t=size[ch[r][0]]+1;
    if(t==k)return r;
    if(t>k)return Get_Kth(ch[r][0],k);
    else return Get_Kth(ch[r][1],k-t);
}

//在第pos个数后插入tot个数
void Insert(int pos,int tot)
{
    for(int i=0;i<tot;i++)scanf("%d",&a[i]);
    Splay(Get_Kth(root,pos+1),0);
    Splay(Get_Kth(root,pos+2),root);
    Build(Key_value,0,tot-1,ch[root][1]);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
void erase(int r)
{
    if(!r)return;
    s[++tot2]=r;
    erase(ch[r][0]);
    erase(ch[r][1]);
}
//从第pos个数开始连续删除tot个数
void Delete(int pos,int tot)
{
    Splay(Get_Kth(root,pos),0);
    Splay(Get_Kth(root,pos+tot+1),root);
    erase(Key_value);
    pre[Key_value]=0;
    Key_value=0;
    Push_Up(ch[root][1]);
    Push_Up(root);
}
//从第pos个数连续开始的tot个数修改为c
void Make_Same(int pos,int tot,int c)
{
    Splay(Get_Kth(root,pos),0);
    Splay(Get_Kth(root,pos+tot+1),root);
    Update_Same(Key_value,c);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
//反转
void Reverse(int pos,int tot)
{
    Splay(Get_Kth(root,pos),0);
    Splay(Get_Kth(root,pos+tot+1),root);
    Update_Rev(Key_value);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
//求和
int Get_Sum(int pos,int tot)
{
    Splay(Get_Kth(root,pos),0);
    Splay(Get_Kth(root,pos+tot+1),root);
    return sum[Key_value];
}
//得到最大和
int Get_MaxSum(int pos,int tot)
{
    Splay(Get_Kth(root,pos),0);
    Splay(Get_Kth(root,pos+tot+1),root);
    return mx[Key_value];
}
void Inorder(int r)
{
    if(!r)return;
    Push_Down(r);
    Inorder(ch[r][0]);
    printf("%d ",key[r]);
    Inorder(ch[r][1]);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&q)==2)
    {
        Init();
        char op[20];
        int x,y,z;
        while(q--)
        {
            scanf("%s",op);
            if(op[0]=='I')
            {
                scanf("%d%d",&x,&y);
                Insert(x,y);
            }
            else if(op[0]=='D')
            {
                scanf("%d%d",&x,&y);
                Delete(x,y);
            }
            else if(op[0]=='M'&&op[2]=='K')
            {
                scanf("%d%d%d",&x,&y,&z);
                Make_Same(x,y,z);
            }
            else if(op[0]=='R')
            {
                scanf("%d%d",&x,&y);
                Reverse(x,y);
            }
            else if(op[0]=='G')
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",Get_Sum(x,y));
            }
            else
            {
                printf("%d\n",Get_MaxSum(1,size[root]-2));
            }
        }
    }
    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
/*题目：给一棵边权无根树，问是否有点对距离为k
思路：暴力枚举所有点对，复杂度O(n^2logn)
有性质：任意点对的距离，
要么经过根节点
要么不经过根结点
经过根结点时 dis(u,v) = dis(u,rt) + dis(rt,v)
不经过时，我们递归讨论。
如果递归层数过大，复杂度任然爆炸。
有结论：找到树的重心后，均摊复杂度nlogn。*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
/**
设根为rt，子树为v1..vi,求出vi中每个结点到rt的距离保存到rem
pd[dis]表示在v1..vi-1有没有到rt距离为dis的
那么如果rem[x]+pd[dis]满足，则表示该询问的路径存在
将所有子树清空后清空数组
**/
int n,m;
int rt,sum,f[maxn];
int head[maxn],ecnt;
struct edge{int to,nxt,w;}e[maxn<<1];
void adde(int u,int v,int w){
    e[++ecnt]={v,head[u],w};head[u]=ecnt;
}
int qr[maxn],vs[maxn];
int vis[maxn],siz[maxn];
int dis[maxn];
int pd[maxn];
void getroot(int u,int pre){
    f[u]=0,siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre||vis[v])continue;
        getroot(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }f[u]=max(f[u],sum-siz[u]);
    if(f[u]<f[rt])rt=u;
}
int rem[maxn],q[maxn];
void getdis(int u,int fa){
    rem[++rem[0]]=dis[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+e[i].w;
        getdis(v,u);
    }
}
void calc(int u){
    int p=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        rem[0]=0;dis[v]=e[i].w;
        getdis(v,u);//处理每个子树的dis
        for(int j=rem[0];j;--j){
            for(int k=1;k<=m;++k){
                if(qr[k]>=rem[j])vs[k]|=pd[qr[k]-rem[j]];
                //如果存在，标记答案
            }
        }
        for(int j=rem[0];j;--j){
            q[++p]=rem[j],pd[rem[j]]=1;//把出现过的dis保存到pd里
        }
    }
    for(int i=1;i<=p;++i)pd[q[i]]=0;//清空pd
}
void solve(int u){
    vis[u]=pd[0]=1;calc(u);//pd[i]表示到根距离为i的路径是否存在
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        f[0]=n;sum=siz[v];rt=0;
        getroot(v,0);solve(rt);//在子树找到重心并递归处理
    }
}
int main(){
    scanf("%d%d",&n,&m);
    f[0]=sum=n;
    int u,v,w;
    for(int i=2;i<=n;++i){
        scanf("%d%d%d",&u,&v,&w);adde(u,v,w);adde(v,u,w);
    }
    for(int i=1;i<=m;++i)scanf("%d",qr+i);//离线查询
    rt=0;getroot(1,0);solve(rt);//找整个树的重心，然后分治
    for(int i=1;i<=m;++i)puts(vs[i]?"AYE":"NAY");
    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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10005;
struct edge{int to,next,w;}a[N<<1];
int n,m,k,head[N],cnt,root,sum,vis[N],sz[N],f[N],dep[N],o[N],ans;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
void getroot(int u,int fa){
    sz[u]=1;f[u]=0;
    for (int e=head[u];e;e=a[e].next){
        int v=a[e].to;if (v==fa||vis[v]) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sum-sz[u]);
    if (f[u]<f[root]) root=u;
}
void getdeep(int u,int fa){
    o[++cnt]=dep[u];
    for (int e=head[u];e;e=a[e].next){
        int v=a[e].to;if (v==fa||vis[v]) continue;
        dep[v]=dep[u]+a[e].w;getdeep(v,u);
    }
}
int calc(int u,int d0){
    cnt=0;dep[u]=d0;
    getdeep(u,0);
    sort(o+1,o+cnt+1);
    int l=1,r=cnt,res=0;
    while (l<r)
        if (o[l]+o[r]<=k) res+=r-l,l++;
        else r--;
    return res;
}
void solve(int u){
    ans+=calc(u,0);
    vis[u]=1;
    for (int e=head[u];e;e=a[e].next){
        int v=a[e].to;if (vis[v]) continue;
        ans-=calc(v,a[e].w);
        sum=sz[v];root=0;
        getroot(v,0);
        solve(root);
    }
}
int main(){
    while (1){
        n=gi();k=gi();
        if (n==0&&k==0) return 0;
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=0;ans=0;
        for (int i=1,u,v,w;i<n;i++){
            u=gi();v=gi();w=gi();
            a[++cnt]=(edge){v,head[u],w};head[u]=cnt;
            a[++cnt]=(edge){u,head[v],w};head[v]=cnt;
        }
        root=0;sum=f[0]=n;
        getroot(1,0);solve(root);
        printf("%d\n",ans);
    }
}

距离为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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e4+10;

int n;
int rt,sum,f[maxn];
int head[maxn],ecnt;
struct edge{int to,nxt,w;}e[maxn<<1];
void adde(int u,int v,int w){
    e[++ecnt]={v,head[u],w};head[u]=ecnt;
}
int vis[maxn],dis[maxn],pd[5],siz[maxn];
void getroot(int u,int pre){
    f[u]=0;siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre||vis[v])continue;
        getroot(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }f[u]=max(f[u],sum-siz[u]);
    if(f[u]<f[rt])rt=u;
}
void getdis(int u,int fa){
    ++pd[dis[u]];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v])continue;
        (dis[v]=dis[u]+e[i].w)%=3;
        getdis(v,u);
    }
}
int calc(int u,int w){
    memset(pd,0,sizeof pd);
    dis[u]=w;
    getdis(u,0);
    return 2*pd[1]*pd[2] + pd[0]*pd[0];
}
int ans = 0;
void solve(int u){
    ans += calc(u,0);
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        ans -= calc(v,e[i].w);
        rt=0;sum=siz[v];getroot(v,u);solve(rt);
    }
}
int main(){
    scanf("%d",&n);
    int u,v,w;
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&u,&v,&w);w%=3;
        adde(u,v,w);adde(v,u,w);
    }
    sum=f[0]=n;rt=0;
    getroot(1,0);
    solve(rt);
    int fm = n*n;
    int gc = __gcd(fm,ans);
    ans/=gc;fm/=gc;
    printf("%d/%d",ans,fm);
    return 0;
}

CDQ分治

2018湖南省赛，线段覆盖问题。

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
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int maxn = 1e5+10;
struct Node{
    int idx,l,r,delt;
    int kind;
    bool operator < (const Node &rhs)const{
        return l<rhs.l;
    }
}node[maxn];

int ans[maxn],del[maxn];
/*******反向BIT*******/
inline int lowbit(int x){return x&(-x);}
int arr[maxn],MAX;
void add(int x,int d){
    while(x){
        arr[x]+=d;
        x-=lowbit(x);
    }
}
int sum(int x){
    int ret=0;
    while(x<=MAX){
        ret+=arr[x];
        x+=lowbit(x);
    }return ret;
}
/****离散化****/
int vec[maxn],vec_idx;
int hs(int x){
    return lower_bound(vec,vec+vec_idx,x)-vec+1;
}
/*****CDQ*****/
void cdq(int l,int r){
    if(l==r)return;
    int mid = (l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int j=l;
    for(int i=mid+1;i<=r;i++){
        if(node[i].kind==2){
            for(;j<=mid && node[j].l<=node[i].l;j++){
                if(node[j].kind==1){
                    add(hs(node[j].r),node[j].delt);
                }
            }
            ans[node[i].idx]+=sum(hs(node[i].r));
        }
    }
    for(int i=l;i<j;i++){
        if(node[i].kind==1){
            add(hs(node[i].r),-node[i].delt);
        }
    }
    inplace_merge(node+l,node+mid+1,node+r+1);
}
int vis[maxn];
int main(){
    int n,m;
    while(scanf("%d%d",&m,&n)!=EOF){
        int cnt=0;
        vec_idx=0;
        memset(arr,0,sizeof(arr));
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        vector<int> v;
        char op[3];
        for(int i=1;i<=n;i++){
            scanf("%s",op);
            if(op[0]=='1'){
                scanf("%d%d",&node[i].l,&node[i].r);
                node[i].kind=1;
                node[i].idx=i;
                node[i].delt=1;
                vec[vec_idx++]=node[i].r;
                v.push_back(i);
            } else if(op[0]=='2'){
                scanf("%d%d",&node[i].l,&node[i].r);
                node[i].kind=2;
                node[i].idx=i;
                vec[vec_idx++]=node[i].r;
                vis[i]=1;
            } else{
                int tmp;
                scanf("%d",&tmp);
                node[i].kind=1;
                node[i].l=node[v[tmp-1]].l;
                node[i].r=node[v[tmp-1]].r;
                node[i].delt=-1;
                node[i].idx=i;
            }
        }
        sort(vec,vec+vec_idx);
        MAX = vec_idx+10;
        cdq(1,n);
        for(int i=1;i<=n;i++){
            if(vis[i]){
                printf("%d\n",ans[i]);
            }
        }
    }
    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
/*
给定N个三维的点，问对于点i，
有多少个点三个坐标都小于点i(1<=i<=n)
*/
using namespace std;
#define N 100010
struct rec{
    int x,y,z,id;
    bool operator==(const rec &a){
        return x==a.x&&y==a.y&&z==a.z;
    }
}a[N],tmp[N];
int ans[N],c[N];
int n;
bool cmp1(rec &a,rec &b){
    if(a==b) return a.id<b.id;
    return a.x<b.x||a.x==b.x&&a.y<b.y||a.x==b.x&&a.y==b.y&&a.z<b.z;
}
bool cmp2(rec &a,rec &b){
    return a.y<b.y||a.y==b.y&&a.id<b.id;
}
inline void add(int x,int w){
    for(;x<=100000;x+=x&-x) c[x]+=w;
}
inline int getsum(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}
void solve(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    for(int i=l;i<=r;++i) tmp[i]=a[i];
    sort(a+l,a+mid+1,cmp2);
    sort(a+mid+1,a+r+1,cmp2);
    int ll=l;
    for(int i=mid+1;i<=r;++i){
        while(ll<=mid&&a[ll].y<=a[i].y) add(a[ll++].z,1);
        ans[a[i].id]+=getsum(a[i].z);
    }
    for(int i=l;i<ll;++i) add(a[i].z,-1);
    for(int i=l;i<=r;++i) a[i]=tmp[i];
    solve(l,mid);solve(mid+1,r);
}
int main(){
    int ca;
    scanf("%d",&ca);
    while(ca--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            a[i].id=i;
        }
        sort(a+1,a+n+1,cmp1);
        memset(ans,0,sizeof(ans));
        solve(1,n);
        for(int i=n-1;i>0;--i)
            if(a[i]==a[i+1]) ans[a[i].id]=ans[a[i+1].id];
        for(int i=1;i<=n;++i)
            printf("%d\n",ans[i]);
    }
    return 0;
}

三维LIS

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
/*
给定n个三维坐标，求其LIS及其数量，
当x1<=x2,y1<=y2,z1<=z2是，p1<=p2。
先排序掉一维，然后剩下两维分治，
用一个带长度和方案数的结构体树状数组维护。
*/
using namespace std;
#define N 100010
const int mod=(1<<30)-1;
struct Point{
    int x,y,z,id;
}q[N],tmp[N];
struct rec{
    int len,num;
    void init() {
        len=num=0;
    }
}dp[N],c[N];
int a[N];
int n,tot;
void updata(rec &a,rec b){
    if(a.len<b.len) a=b;
    else if(a.len==b.len) a.num+=b.num,a.num&=mod;
}
void add(int x,const rec &a){
    for(;x<=tot;x+=x&-x) updata(c[x],a);
}
rec getmax(int x){
    rec ans;ans.init();
    for(;x;x-=x&-x) updata(ans,c[x]);
    return ans;
}
void clr(int x){
    for(;x<=tot;x+=x&-x) c[x].init();
}
bool cmp1(Point &p1,Point &p2){
    return p1.x<p2.x||p1.x==p2.x&&p1.y<p2.y||p1.x==p2.x&&p1.y==p2.y&&p1.z<p2.z;
}
bool cmp2(Point &p1,Point &p2){
    return p1.y<p2.y||p1.y==p2.y&&p1.id<p2.id;
}
void solve(int s,int t){
    if(s==t) return;
    int mid=s+t>>1;
    solve(s,mid);
    for(int i=s;i<=t;++i) tmp[i]=q[i];
    sort(tmp+s,tmp+t+1,cmp2);
    rec ans;
    for(int i=s;i<=t;++i)
        if(tmp[i].id<=mid)
            add(tmp[i].z,dp[tmp[i].id]);
        else{
            ans=getmax(tmp[i].z);++ans.len;
            updata(dp[tmp[i].id],ans);
        }
    for(int i=s;i<=t;++i)
        if(tmp[i].id<=mid) clr(tmp[i].z);
    solve(mid+1,t);
}
int main(){
    int ca;
    scanf("%d",&ca);
    while(ca--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
            a[i]=q[i].z;dp[i].len=dp[i].num=1;
        }
        sort(a+1,a+n+1);
        tot=unique(a+1,a+n+1)-a-1;
        for(int i=1;i<=n;++i)
            q[i].z=lower_bound(a+1,a+tot+1,q[i].z)-a;
        sort(q+1,q+n+1,cmp1);
        for(int i=1;i<=n;++i) q[i].id=i;
        solve(1,n);
        rec ans;ans.init();
        for(int i=1;i<=n;++i) updata(ans,dp[i]);
        printf("%d %d\n",ans.len,ans.num);
    }
    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
/*
1 x y z 添加一个点
2 x1 y1 z1 x2 y2 z2 查找长方体内点的数量
CDQ分治套CDQ分治套树状数组
第一重CDQ分治计算左边的修改对右边的询问的影响，
第二重CDQ分治处理三维偏序问题
*/
using namespace std;
#define N 50010
struct rec{
    int k,x,y,z,w,id;
    rec(){}
    rec(int k,int x,int y,int z,int w,int id):
        k(k),x(x),y(y),z(z),w(w),id(id){}
    bool operator==(const rec &a){
        return x==a.x&&y==a.y&&z==a.z;
    }
}q[N*8],qq[N*8],tmp[N*8];
int ans[N],tree[N*2],a[N*2],b[N*2],c[N*2],kind[N];
int n,ta,tb,tc;
bool cmp1(rec &a,rec &b){
    if(a==b) return a.id<b.id;
    return a.x<b.x||a.x==b.x&&a.y<b.y||a.x==b.x&&a.y==b.y&&a.z<b.z;
}
bool cmp2(rec &a,rec &b){
    return a.y<b.y;
}
inline void add(int x,int w){
    for(;x<=tc;x+=x&-x) tree[x]+=w;
}
inline int getsum(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=tree[x];
    return ans;
}
void cdq(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    for(int i=l;i<=r;++i) tmp[i]=qq[i];
    sort(qq+l,qq+mid+1,cmp2);
    sort(qq+mid+1,qq+r+1,cmp2);
    int ll=l;
    for(int i=mid+1;i<=r;++i){
        while(ll<=mid&&qq[ll].y<=qq[i].y){
            if(qq[ll].k==1) add(qq[ll].z,1);
            ++ll;
        }
        if(qq[i].k==2) ans[qq[i].id]+=getsum(qq[i].z)*qq[i].w;
    }
    for(int i=l;i<ll;++i)
        if(qq[i].k==1) add(qq[i].z,-1);
    for(int i=l;i<=r;++i) qq[i]=tmp[i];
    cdq(l,mid);cdq(mid+1,r);
}
void solve(int l,int r){
    if(l==r) return;
    int mid=l+r>>1,n=0;
    for(int i=l;i<=mid;++i)
        if(q[i].k==1) qq[++n]=q[i];
    for(int i=mid+1;i<=r;++i)
        if(q[i].k==2) qq[++n]=q[i];
    if(n){
        sort(qq+1,qq+n+1,cmp1);
        cdq(1,n);
    }
    solve(l,mid);solve(mid+1,r);
}
int main(){
    int ca;
    scanf("%d",&ca);
    while(ca--){
        scanf("%d",&n);
        int nn=0,k,a1,b1,c1,a2,b2,c2;
        ta=tb=tc=0;
        for(int i=1;i<=n;++i){
            scanf("%d%d%d%d",&k,&a1,&b1,&c1);
            kind[i]=k;
            if(k==1){
                q[++nn]=rec(k,a1,b1,c1,1,i);
                c[++tc]=c1;
            }
            else{
                scanf("%d%d%d",&a2,&b2,&c2);
                --a1;--b1;--c1;
                c[++tc]=c1;c[++tc]=c2;
                q[++nn]=rec(k,a2,b2,c2,1,i);
                q[++nn]=rec(k,a1,b2,c2,-1,i);
                q[++nn]=rec(k,a2,b1,c2,-1,i);
                q[++nn]=rec(k,a2,b2,c1,-1,i);
                q[++nn]=rec(k,a1,b1,c2,1,i);
                q[++nn]=rec(k,a1,b2,c1,1,i);
                q[++nn]=rec(k,a2,b1,c1,1,i);
                q[++nn]=rec(k,a1,b1,c1,-1,i);
            }
        }
        sort(c+1,c+tc+1);tc=unique(c+1,c+tc+1)-c-1;
        for(int i=1;i<=nn;++i)
            q[i].z=lower_bound(c+1,c+tc+1,q[i].z)-c;
        memset(ans,0,sizeof(ans));
        solve(1,nn);
        for(int i=1;i<=n;++i)
            if(kind[i]==2) printf("%d\n",ans[i]);
    }
    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
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef int LL;
#define dd c=getchar()
inline LL read(){LL a=0,b=1;char dd;while(!isdigit(c)&&c!='-')dd;
    if(c=='-'){b=-b;dd;}while(isdigit(c)){a=a*10+c-'0';dd;}return a*b;}
#undef dd
template <int n>
class vervec{
LL tree[20*n],ls[20*n],rs[20*n],hd[n],hd1[2*n],tt,t,nh;LL*a;
LL&ins(LL nod,LL l,LL r,LL x){/**  **/
    if(l==r){return tree[nod];}
    int mid=l+r>>1;
    if(x<=mid){tree[++tt]=tree[ls[nod]];ls[tt]=ls[ls[nod]];rs[tt]=rs[ls[nod]];
        ls[nod]=tt;return ins(tt,l,mid,x);}
    if(x>mid){tree[++tt]=tree[rs[nod]];ls[tt]=ls[rs[nod]];rs[tt]=rs[rs[nod]];
        rs[nod]=tt;return ins(tt,mid+1,r,x);}
}
void chit(){LL x=hd[nh];hd[++t]=++tt;tree[tt]=tree[x];
    ls[tt]=ls[x];rs[tt]=rs[x];nh=t;}
int build(LL l,LL r){/**主席树建树**/
    LL nod=++tt;if(l==r){tree[nod]=a[l];ls[nod]=rs[nod]=0;return nod;}
    LL mid=l+r>>1;
    ls[nod]=build(l,mid);
    rs[nod]=build(mid+1,r);
    return nod;
}
void init(){tt=0;hd[nh=0]=1;build(1,n);}/**清空并建树**/
LL query(LL nod,LL l,LL r,LL x){
    if(l==r)return tree[nod];
    LL mid=l+r>>1;
    if(x<=mid)return query(ls[nod],l,mid,x);
    else if(x>mid)return query(rs[nod],mid+1,r,x);
}
public:
    vervec(){tt=0;t=0;nh=1;}
    void init(LL*x){a=x;init();}
    void mark(LL x){hd1[x]=nh;}/**修改当前时间戳**/
    LL&operator[](LL x){chit();return ins(hd[nh],1,n,x);}
    LL val(LL x){return query(hd[nh],1,n,x);}
    void rever(LL x){nh=hd1[x];}
};
vervec<120003>f,c;
LL getf(LL v){
    LL fa=f.val(v);
    if(fa==v)return v;
    return getf(fa);
}
void add(LL a,LL b){/**启发式合并**/
    a=getf(a);
    b=getf(b);
    if(a==b)return;
    LL va=c.val(a),vb=c.val(b);
    if(va==vb){
        f[a]=b;
        c[b]++;
    }else if(va<vb){
        f[a]=b;
    }else{
        f[b]=a;
    }
}
LL sol[120003],n,m,x,y,z;
void init(LL n){
    for(LL i=1;i<=n;i++)sol[i]=i;/****初始集合为i*****/
    f.init(sol);                 /**建树**/
    for(LL i=1;i<=n;i++)sol[i]=1;
    c.init(sol);
}
int main(){
    n=read();
    m=read();           /***n个集合，m个操作***/
    init(n);
    f.mark(0);
    c.mark(0);
    for(LL i=1;i<=m;i++){
        x=read();
        if(x==1){       /***合并两个集合***/
            x=read();
            y=read();
            add(x,y);
        }else if(x==2){ /***回退到第k次操作的状态***/
            y=read();
            f.rever(y);
            c.rever(y);
        }else{          /*****询问两个集合是否是同一个集合******/
            x=read();
            y=read();
            puts(getf(x)==getf(y)?"1":"0");
        }
        f.mark(i);
        c.mark(i);
    }
    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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
//union find
int f[N];
void INIT(int size)
{ for(int i=0;i<=size;i++) f[i]=i; }
int findf(int x)
{ while(f[x]!=x) x=f[x]; return x; }
void setroot(int x)
{ if(f[x]!=x) setroot(f[x]); f[x]=f[f[x]]=x; }
void link(int a,int b)
{ setroot(a); f[a]=b; }
void cut(int a,int b)
{ setroot(a); f[b]=b; }
char op[10];
int main(){
    int n,a,b;
    scanf("%d",&n);
    INIT(n);
    while(scanf("%s",op)&&op[0]!='E') {
        scanf("%d%d",&a,&b);
        if(op[0]=='C') link(a,b);
        else if(op[0]=='D')cut(a,b);
        else {
            if(findf(a)==findf(b))puts("YES");
            else puts("NO");
            fflush(stdout);
        }
    }
    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
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
const int inf=1e9;
struct rec{
    int w,id;
    rec(){}
    rec(int w,int id):w(w),id(id){}
    bool operator<(const rec a)const
    {
        return w<a.w;
    }
}a[N];
struct interval{
    int l,r,k,id,cnt;
}q[N],tmp[N];
int n,m;
int c[N],ans[N];
inline void add(int x,int w)
{
    for(;x<=n;x+=x&-x) c[x]+=w;
}
inline int getsum(int x)
{
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}
void calc(int s,int t,int l,int r)
{
    int x=lower_bound(a+1,a+n+1,rec(l,0))-a;
    for(int i=x;i<=n&&a[i].w<=r;++i) add(a[i].id,1);
    for(int i=s;i<=t;++i)
        q[i].cnt=getsum(q[i].r)-getsum(q[i].l-1);
    for(int i=x;i<=n&&a[i].w<=r;++i) add(a[i].id,-1);
}
void solve(int s,int t,int l,int r)
{
    if(l==r)
    {
        for(int i=s;i<=t;++i) ans[q[i].id]=l;
        return;
    }
    int mid=l+(r-l>>1);
    calc(s,t,l,mid);
    int ss=s-1,tt=t+1;
    for(int i=s;i<=t;++i)
    {
        if(q[i].cnt>=q[i].k) tmp[++ss]=q[i];
        else q[i].k-=q[i].cnt,tmp[--tt]=q[i];
    }
    for(int i=s;i<=t;++i) q[i]=tmp[i];
    if(ss>=s) solve(s,ss,l,mid);
    if(tt<=t) solve(tt,t,mid+1,r);
}
bool cmp(rec a,rec b)
{
    return a.w<b.w;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i].w);a[i].id=i;
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
            q[i].cnt=0;q[i].id=i;
        }
        solve(1,m,-inf,inf);
        for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    }
    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
75
76
77
78
79
80
81
82
using namespace std;
#define N 100010
struct rec{
    int x,y,k,cnt,id;
    rec(){}
    rec(int x,int y,int k,int cnt,int id):
        x(x),y(y),k(k),cnt(cnt),id(id){}
}q[N*3],q1[N*3],q2[N*3];
const int inf=1e9;
int a[N],ans[N*3],c[N];
int n,m,nn;
inline void add(int x,int w){
    for(;x<=n;x+=x&-x) c[x]+=w;
}
inline int getsum(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}
void calc(int s,int t,int l,int r){
    for(int i=s;i<=t;++i){
        if(q[i].k) q[i].cnt=getsum(q[i].y)-getsum(q[i].x-1);
        else if(q[i].y<=r) add(q[i].x,q[i].cnt);
    }
    for(int i=s;i<=t;++i)
        if(!q[i].k&&q[i].y<=r) add(q[i].x,-q[i].cnt);
}
void solve(int s,int t,int l,int r){
    if(l==r){
        for(int i=s;i<=t;++i)
            if(q[i].k) ans[q[i].id]=l;
        return;
    }
    int mid=l+(r-l>>1);
    calc(s,t,l,mid);
    int t1=0,t2=0;
    for(int i=s;i<=t;++i){
        if(q[i].k){
            if(q[i].cnt>=q[i].k) q1[++t1]=q[i];
            else q[i].k-=q[i].cnt,q2[++t2]=q[i];
        }
        else{
            if(q[i].y<=mid) q1[++t1]=q[i];
            else q2[++t2]=q[i];
        }
    }
    for(int i=1;i<=t1;++i) q[s+i-1]=q1[i];
    for(int i=1;i<=t2;++i) q[t-t2+i]=q2[i];
    if(t1) solve(s,s+t1-1,l,mid);
    if(t2) solve(s+t1,t,mid+1,r);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            q[i]=rec(i,a[i],0,1,i);
            ans[i]=0;
        }
        nn=n;
        scanf("%d",&m);
        int x,y,k,z;
        for(int i=1;i<=m;++i){
            scanf("%d%d%d",&z,&x,&y);
            if(z==1){
                ++nn;q[nn]=rec(x,a[x],0,-1,nn);
                ++nn;q[nn]=rec(x,y,0,1,nn);
                a[x]=y;
                ans[nn]=0;
            }
            else {
                scanf("%d",&k);
                ++nn;q[nn]=rec(x,y,k,0,nn);
            }
        }
        memset(ans,0,sizeof(ans));
        solve(1,nn,1,inf);
        for(int i=1;i<=nn;++i)
            if(ans[i]) printf("%d\n",ans[i]);
    }
    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
/**
笛卡尔树模板
1.值域是堆，下标是二叉搜索树
2.中序遍历就是原序列，构造O(n)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int stk[maxn],tp;
void build(int n,int a[],int ch[][2],int fa[]){
    tp=0;
    for(int i=1;i<=n;++i){
        int last=0;
        while(tp){
            if(a[stk[tp]]<=a[i]){
                if(ch[stk[tp]][1])
                    ch[i][0]=ch[stk[tp]][1],fa[ch[stk[tp]][1]]=i;
                ch[stk[tp]][1]=i;fa[i]=stk[tp];
                break;
            }last=stk[tp--];
        }
        if(!tp&&last)ch[i][0]=last,fa[last]=i;
        stk[++tp]=i;
    }
}
int n,a[maxn],b[maxn],fa[maxn],ch[maxn][2],faa[maxn],chh[maxn][2];
bool d(int x){return ch[fa[x]][1]==x;}
int query(int x,int v){while(fa[x]&&d(x)==v)x=fa[x];return fa[x];}
void dfs(int rt){
    if(!a[rt])return;
    dfs(ch[rt][0]);
    cout<<fa[rt]<<" "<<a[rt]<<endl;
    dfs(ch[rt][1]);
}

bool ok(int len){
    for(int i=1;i<=len;++i){
        fa[i]=faa[i]=0;ch[i][0]=ch[i][1]=0;
        chh[i][0]=chh[i][1]=0;
    }
    build(len,a,ch,fa);
    build(len,b,chh,faa);
    for(int i=1;i<=len;++i){
        if(fa[i]!=faa[i])return 0;
        if(ch[i][0]!=chh[i][0])return 0;
        if(ch[i][1]!=chh[i][1])return 0;
    }return 1;
}
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        for(int i=1;i<=n;i++)scanf("%d",b+i);
        int low=0,high=n+1;
        while(high-low>1){
            int mid=low+high>>1;
            if(ok(mid))low=mid;
            else high=mid;
        }cout<<low<<endl;
    }
    return 0;
}

字典树

01 trie

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int n,head[maxn],cnt,val[maxn];
struct edge{
    int nxt,to,w;
}e[maxn<<1];
void adde(int u,int v,int w){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
void dfs(int u,int pre,int v){
    val[u]=v;
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].to==pre)continue;
        dfs(e[i].to,u,v^e[i].w);
    }
}
int ans=0;
int son[maxn*30+5][2],tot;
void ask(int x){
    int u=0,tmp=0;
    for(int i=30;i>=0;i--){
        bool c=(((1<<i)&x)!=0);
        if(son[u][!c]){
            tmp|=(1<<i);u=son[u][!c];
        } else {
            u=son[u][c];
        }
    }ans=max(ans,tmp);
}
void ins(int x){
    int u=0;
    for(int i=30;i>=0;i--){
        bool c=(((1<<i)&x)!=0);//当前这位是1还是0
        if(!son[u][c])son[u][c]=++tot;//出没出现过，没出现过就新建节点
        u=son[u][c];
    }
}
int main(){
    scanf("%d",&n);
    int u,v,w;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);adde(v,u,w);
    }
    dfs(1,0,0);
    for(int i=1;i<=n;i++){
        ask(val[i]);ins(val[i]);
    }cout<<ans;
    return 0;
}

可持久化trie树

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 6e5+10;
int las=0;
int n,m,son[maxn*24*2][2],siz[maxn*24*2],tot,ttot;
int T[maxn];
void ins(int x){
    int rt=T[ttot];
    T[++ttot]=++tot;
    int nrt=tot;
    for(int i=24;i>=0;i--){
        bool c=(x>>i)&1;
        son[nrt][c]=++tot;
        son[nrt][!c]=son[rt][!c];
        rt=son[rt][c];nrt=son[nrt][c];
        siz[nrt]=siz[rt]+1;
    }
}
int ask(int lrt,int rrt,int x){
    int ret=0;
    for(int i=24;i>=0;i--){
        bool c=(x>>i)&1;
        if(siz[son[rrt][!c]] - siz[son[lrt][!c]] >0 ){
            ret|=(1<<i);
            lrt=son[lrt][!c];rrt=son[rrt][!c];
        } else {
            lrt=son[lrt][c];rrt=son[rrt][c];
        }
    }return ret;
}
int main(){
	scanf("%d%d",&n,&m);
	int x;
	ins(las);
	for(int i=1;i<=n;i++){
        scanf("%d",&x);las^=x;ins(las);
	}
	char op[2];int l,r;
	while(m--){
        scanf("%s",op);
        if(op[0]=='A'){
            scanf("%d",&x);las^=x;ins(las);
        }
        else{
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",ask(T[l-1],T[r],las^x));
        }
	}
	return 0;
}

string

kmp

牛客多校带回退的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
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
#include <bits/stdc++.h>
using namespace std;
int n;
int len[5];
int ans[100005];
char ch[5][100005];
char pro[100005];
int f[100005];
int f2[100005];
int lenp;
int q[100005];
void getfail(char *p,int len){
    f[0]=f[1]=f2[0]=f2[1]=0;
    for(int i=1;i<len;i++){
        int j=f2[i];
        while(j&&p[i]!=p[j])j=f2[j];
        f2[i+1] = f[i+1] = (p[i]==p[j])?j+1:0;
        if(f[i+1]==j+1 && p[i+1]==p[j+1])f[i+1]=f[j+1];
    }
    /**
    带退格的优化kmp：
    当在p[i+1]的位置失配的时候，如果普通kmp的p[i+1]指向p[j+1]
    并且他们相同，那么下次匹配依旧还是失配的，就会继续跳到p[f[j+1]]
    如此下来失配的时候刚好会跳到本该在的位置
    **/
}
void kmp(char *t,char *s,int id){
    getfail(s,len[id]);
    int j=0;
    q[0]=0;
    int r=0;
    for(int i=0;i<lenp;i++){
        if(t[i]=='-'){
            if(r)r--;
            j=q[r];
        }
        else{
            while(j&&s[j]!=t[i])j=f[j];
            if(s[j]==t[i])j++;
            q[++r]=j;
        }
        ans[i] = min(ans[i] , len[id] - q[r]);
    }
}
int main(){
    scanf("%d",&n);
    int temp=0x3f3f3f3f;
    for(int i=0;i<n;i++){
        scanf("%s",ch[i]);
        len[i]=strlen(ch[i]);
        temp=min(temp,len[i]);
    }
    printf("%d\n",temp);
    memset(ans,0x3f,sizeof ans);
    scanf("%s",pro);
    lenp=strlen(pro);
    for(int i=0;i<n;i++){
        kmp(pro,ch[i],i);
    }
    for(int i=0;i<lenp;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef long long ll;
const int maxn = 2e5+10;
char s[maxn];
const int base = 233;
const int mod = 1e9+21;
int po[maxn],hs[maxn];
inline int md(ll x){
    return x>=mod?x%mod:x;
}
inline int geth(int l,int r){
    int ret = hs[r]-md((ll)hs[l-1]*po[r-l+1]);
    return ret<0?ret+mod:ret;
}
int main(){
    scanf("%s",s+1);len=strlen(s+1);
    po[0]=1;
    for(int i=1;i<=len;++i){
        hs[i]=md((ll)hs[i-1]*base + s[i]);
        po[i]=md((ll)po[i-1]*base);
    }
    return 0;
}

manacher

南京现场赛manacher + exkmp

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+10;
char Ma[maxn<<1];
int Mp[maxn<<1];
void manacher(char s[],int len){
    int l=0;
    Ma[l++]='$';
    Ma[l++]='#';
    for(int i=0;i<len;i++){
        Ma[l++]=s[i];
        Ma[l++]='#';
    }
    Ma[l]=0;
    int mx=0,id=0;
    for(int i=0;i<l;i++){
        Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;
        if(i+Mp[i]>mx){
            mx=i+Mp[i];
            id=i;
        }
    }
}
void pre_EKMP(char x[],int m,int next[])
{
    next[0]=m;
    int j=0;
    while(j+1<m && x[j]==x[j+1])j++;
    next[1]=j;
    int k=1;
    for(int i=2; i<m; i++)
    {
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)next[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<m && x[i+j]==x[j])j++;
            next[i]=j;
            k=i;
        }
    }
}
void EKMP(char x[],int m,char y[],int n,int next[],int extend[])
{
    pre_EKMP(x,m,next);
    int j=0;
    while(j<n && j<m && x[j]==y[j])j++;
    extend[0]=j;
    int k=0;
    for(int i=1; i<n; i++)
    {
        int p=extend[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)extend[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<n && j<m && y[i+j]==x[j])j++;
            extend[i]=j;
            k=i;
        }
    }
}
char s[maxn],t[maxn];
int pre[maxn];
int extend[maxn],nxt[maxn];
int main(){
    scanf("%s",s);
    int lens=strlen(s);
    manacher(s,lens);
    for(int i=2;i<2*lens+2;i++){
        if(Mp[i]<2)continue;
        int idx = i/2;
        int id  = idx - Mp[i]/2+1;
        pre[id]++;
        pre[idx+1]--;
    }
    for(int i=1;i<=lens;i++){
        pre[i]+=pre[i-1];
    }
    scanf("%s",t);
    int lent=strlen(t);
    reverse(s,s+lens);
    EKMP(t,lent,s,lens,nxt,extend);
    ll ans=0;
    int j=lens-1;
    for(int i=2;i<=lens;i++){
        ans+=1ll*pre[i]*extend[j];
        j--;
    }
    cout<<ans<<endl;
    return 0;
}

回文自动机

hdu多校第二场的回文串题 pam + 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
72
73
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 26;
const int maxn = 3e5+10;
const int base=31;
ull hs[maxn],ht[maxn],po[maxn];
ull geth(int l,int r){return hs[r]-po[r-l+1]*hs[l-1];}
ull gett(int l,int r){return ht[l]-po[r-l+1]*ht[r+1];}
struct pam{
    int nxt[maxn][N],fail[maxn];//在当前状态首尾添加字符的状态,失配跳到的状态
    int len[maxn],S[maxn],ppos[maxn];//状态i表示的回文长度,缓存池,状态对应首次出现的位置
    int cnt[maxn],num[maxn];//状态出现次数,以状态末尾结尾但不包含本条路径的数目
    int last,n,p;//上个状态,总长度,当前状态编号
    int newnode(int l){
        memset(nxt[p],0,sizeof nxt[p]);
        cnt[p]=num[p]=0;
        len[p]=l;
        return p++;
    }
    void init(){
        p=0;
        newnode(0);newnode(-1);
        last=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,int pos){
        c-='a';
        S[++n]=c;
        int cur=get_fail(last);
        if(!nxt[cur][c]){
            int now=newnode(len[cur]+2);
            ppos[now]=pos;
            fail[now]=nxt[get_fail(fail[cur])][c];
            nxt[cur][c]=now;
            num[now]=num[fail[now]]+1;
        }last=nxt[cur][c];cnt[last]++;
    }
    void Count(){
        for(int i=p-1;i>=0;--i)cnt[fail[i]]+=cnt[i];
    }
}p;
char s[maxn];
ull ans[maxn];
int main(){
    po[0]=1;for(int i=1;i<maxn;++i)po[i]=po[i-1]*base;
    while(scanf("%s",s+1)!=EOF){
        p.init();
        int len=strlen(s+1);
        for(int i=1;i<=len;++i){
            p.add(s[i],i);ans[i]=0;hs[i]=hs[i-1]*base+s[i];
        }ht[len]=s[len];
        for(int i=len-1;i;--i)ht[i]=ht[i+1]*base+s[i];
        p.Count();
        for(int i=2;i<p.p;++i){
            int mid = (2*p.ppos[i]-p.len[i]+1)/2;
            int mmid= (p.ppos[i]-p.len[i]+1+mid)/2;
            if(geth(p.ppos[i]-p.len[i]+1,mmid) == 
            gett(mmid+( (mid - p.ppos[i]-p.len[i] ) %2==0),mid) ){
                ans[p.len[i]]+=p.cnt[i];
            }
        }
        for(int i=1;i<=len;++i){
            printf("%llu%c",ans[i]," \n"[i==len]);
        }
    }
    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
if(len[now]<=2)half[now]=fail[now];
else{
    int tmp=half[cur];
    while( S[n-len[tmp]-1]!=S[n] || (len[tmp]+2)*2 > len[now] )tmp=fail[tmp];
    half[now]=nxt[tmp][c];
}


    int diff[maxn],snext[maxn];
    /**
    diff[x]表示x的最长回文后缀长度减少了多少
    snext[x]表示fail链上第一个diff[y]!=diff[x]的状态
    series[x]表示x -> snext[x]的链
    */
    int f[maxn],series[maxn];
    f[0]=1;
    for(int i=1;i<=n;++i){
        p.add(s[i],i);
        for(int v=p.last;p.len[v]>0;v=p.snext[v]){
            series[v]=f[i-(p.len[p.snext[v]]+p.diff[v])];
            if(p.diff[v]==p.diff[p.fail[v]])
                (series[v]+=series[p.fail[v]])%=mod;
            (f[i]+=series[v])%=mod;
        }if(i&1)f[i]=0;
    }
    cout<<f[n];


	1 - 31 长度的回文串是否存在
	f[0]=1;
	for(int i=1; i<=n; i++) {
		pam.insert(s[i]-'a');
		for(int v=pam.last; pam.len[v]>0; v=pam.snext[v]) {
			series[v]=f[i-(pam.len[pam.snext[v]]+pam.diff[v])];
			if(pam.diff[v]==pam.diff[pam.next[v]])
				series[v]|=series[pam.next[v]];
			f[i]|=series[v]<<1;
		}
		printf("%u\n",f[i]>>1);
	}

后缀数组

sais

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 ll long long
#define re register
#define gc getchar
#define pc putchar
#define cs const
cs int N=4e5;
namespace SA{
    char s[N];
    int sa[N],rk[N],ht[N],len;
    int b[N],wb[N];
    bool t[N<<1];
    inline bool islms(int i,bool *cs t);
    template<class T>
    inline void induced_sort(T s,int len,int siz,int sigma,bool *cs t,int *cs cb,int *cs p);
    template<class T>
    inline void sais(T s,int len,bool *cs t,int *cs b1,int sigma);
    inline void init(char str[],int len);
}
inline bool SA::islms(int i,bool *cs t){
    return i>0&&t[i]&&!t[i-1];
}
template<class T>
inline void SA::induced_sort(T s,int len,int siz,int sigma,bool *cs t,int *cs cb,int *cs p){
    memset(b,0,sigma<<2);
    memset(sa,-1,len<<2);
    for(int re i=0;i<len;++i)++b[s[i]];
    cb[0]=b[0];
    for(int re i=1;i<sigma;++i)cb[i]=cb[i-1]+b[i];
    for(int re i=siz-1;~i;--i)sa[--cb[s[p[i]]]]=p[i];
    for(int re i=1;i<sigma;++i)cb[i]=cb[i-1]+b[i-1];
    for(int re i=0;i<len;++i)if(sa[i]>0&&!t[sa[i]-1])sa[cb[s[sa[i]-1]]++]=sa[i]-1;
    cb[0]=b[0];
    for(int re i=1;i<sigma;++i)cb[i]=cb[i-1]+b[i];
    for(int re i=len-1;~i;--i)if(sa[i]>0&&t[sa[i]-1])sa[--cb[s[sa[i]-1]]]=sa[i]-1;
}
template<class T>
inline void SA::sais(T s,int len,bool *cs t,int *cs b1,int sigma){
    int *cb=b+sigma,siz=0,cnt=0,p=-1;
    t[len-1]=1;
    for(int re i=len-2;~i;--i)t[i]=s[i]==s[i+1]?t[i+1]:(s[i]<s[i+1]);
    for(int re i=1;i<len;++i)if(islms(i,t))b1[siz++]=i;
    induced_sort(s,len,siz,sigma,t,cb,b1);
    for(int re i=siz=0;i<len;++i)if(islms(sa[i],t))sa[siz++]=sa[i];
    memset(sa+siz,-1,(len-siz)<<2);
    for(int re i=0;i<siz;++i){
        re int x=sa[i];
        for(int re j=0;j<len;++j){
            if(p==-1||s[x+j]!=s[p+j]||t[x+j]!=t[p+j]){
                ++cnt;p=x;
                break;
            }
            else if(j>0&&(islms(x+j,t)||islms(p+j,t)))break;
        }
        sa[siz+(x>>1)]=cnt-1;
    }
    for(int re i=len-1,j=len-1;i>=siz;--i)if(~sa[i])sa[j--]=sa[i];
    int *s1=sa+len-siz,*b2=b1+siz;
    if(cnt<siz)sais(s1,siz,t+len,b1+siz,cnt);
    else for(int re i=0;i<siz;++i)sa[s1[i]]=i;
    for(int re i=0;i<siz;++i)b2[i]=b1[sa[i]];
    induced_sort(s,len,siz,sigma,t,cb,b2);
}
inline void SA::init(char str[],int len1){
    memset(ht,0,sizeof ht);
    memset(rk,0,sizeof rk);
    memset(b,0,sizeof b);
    memset(wb,0,sizeof wb);
    memset(t,0,sizeof t);
    sais(s+1,len1+1,t,wb,128);
    rk[0]=0,sa[0]=len1+1;
    for(int re i=1;i<=len1;++i)rk[++sa[i]]=i;
    for(int re i=1,k=0,j=0;i<len1;ht[rk[i++]]=k)
    for(k?--k:0,j=sa[rk[i]-1];s[i+k]==s[j+k];++k);
}
/***/
int RMQ[N],mm[N];
int best[18][N];
void initRMQ(int n){
    mm[0]=-1;
    for(int i=1;i<=n;++i)
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
    for(int i=1;i<=n;i++)best[0][i]=i;
    for(int i=1;i<=mm[n];i++)
        for(int j=1;j+(1<<i)-1<=n;j++){
            int a=best[i-1][j];
            int b=best[i-1][j+(1<<(i-1))];
            if(RMQ[a]<RMQ[b])best[i][j]=a;
            else best[i][j]=b;
        }
}
int askRMQ(int a,int b){
    int t=mm[b-a+1];
    b-=(1<<t)-1;
    a=best[t][a];b=best[t][b];
    return RMQ[a]<RMQ[b]?a:b;
}
int lcp(int a,int b){
    //a=SA::rk[a];b=SA::rk[b];
    if(a>b)swap(a,b);
    return SA::ht[askRMQ(a+1,b)];
}
/***/

下一位置不确定的SA做法

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
char s[maxn+50];
int sa[maxn+50],rk[maxn+50];
int t[maxn+50],t2[maxn+50],c[maxn+50];
int nx[maxn+5][19];
int len,k;
queue<int> q[maxn+5];
void getsa(int m)//m表示最大字符的编码
{
    memset(t,-1,sizeof(t));
    memset(t2,-1,sizeof(t2));
    int *x=t,*y=t2;
    for(int i=0;i<m;++i) c[i]=0;
    for(int i=0;i<len;++i) c[x[i]=s[i]]++;
    for(int i=1;i<m;++i) c[i]+=c[i-1];
    for(int i=len-1;i>=0;--i) sa[--c[x[i]]]=i;
    for(int j=0,k=1;k<=len;k<<=1,++j)
    {
        /*int p=0;
        for(int i=len-k;i<len;++i) y[p++]=i;
        for(int i=0;i<len;++i) if(sa[i]>=k) y[p++]=sa[i]-k;*/

        int p=0;
        for(int i=0;i<len;++i) q[nx[i][j]].push(i);
        for(int i=0;i<len;++i)
            while(!q[sa[i]].empty())
            {
                y[p++]=q[sa[i]].front();
                q[sa[i]].pop();
            }

        for(int i=0;i<m;++i) c[i]=0;
        for(int i=0;i<len;++i) c[x[y[i]]]++;
        for(int i=0;i<m;++i) c[i]+=c[i-1];
        for(int i=len-1;i>=0;--i) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1,x[sa[0]]=0;
        for(int i=1;i<len;++i)
            if(y[sa[i-1]]==y[sa[i]]&&y[nx[sa[i-1]][j]]==y[nx[sa[i]][j]]) x[sa[i]]=p-1;else x[sa[i]]=p++;
        if(p>=len) break;
        m=p;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;++cas)
    {
        printf("Case #%d: ",cas);
        scanf("%d",&len);
        scanf("%s",s);
        for(int i=0;i<len;++i) nx[i][0]=(1LL*i*i+1)%len;
        for(int j=1;j<=18;++j)
            for(int i=0;i<len;++i) nx[i][j]=nx[nx[i][j-1]][j-1];
        getsa('9'+1);
        int pos=sa[len-1];
        for(int i=1;i<=len;++i,pos=nx[pos][0]) printf("%c",s[pos]);
        printf("\n");
    }
   // for(int i=0;i<n;++i) printf("%d ",sa[i]);printf("\n");
   // for(int i=0;i<n;++i) printf("%d ",rk[i]);printf("\n");
   // for(int i=0;i<n;++i) printf("%d ",height[i]);printf("\n");
    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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
char s1[maxn],s2[maxn];
int len1,len2;
pair<int,ll> stk[maxn];
struct SA{
    int rk[maxn],sa[maxn],height[maxn];
    int t1[maxn],t2[maxn],c[maxn];
    bool cmp(int *s,int a,int b,int l){
        return s[a]==s[b]&&s[a+l]==s[b+l];
    }
    void Sa(char *s,int n,int m){
        n++;
        int i,j,p,*x=t1,*y=t2;
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[i]=s[i]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
        for(j=1;j<=n;j<<=1){
            p=0;
            for(i=n-j;i<n;i++)y[p++]=i;
            for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
            for(i=0;i<m;i++)c[i]=0;
            for(i=0;i<n;i++)c[x[y[i]]]++;
            for(i=1;i<m;i++)c[i]+=c[i-1];
            for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=1;x[sa[0]]=0;
            for(i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
            if(p>=n)break;m=p;
        }
        int k=0;n--;
        for(i=0;i<=n;i++)rk[sa[i]]=i;
        for(i=0;i<n;i++){
            if(k)k--;
            j=sa[rk[i]-1];
            while(s[i+k]==s[j+k])k++;
            height[rk[i]]=k;
        }
    }
    void solve(int n){
        ll ret=0;
        int sum[maxn];sum[0]=0;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(sa[i]<len1);
        int top=0;
        stk[0]=make_pair(1,0);
        for(int i=1;i<=n;i++){
            while(top &&height[ stk[top].first ]>height[i])top--;++top;
            stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*height[i]+stk[top-1].second);
            if(sa[i]>len1)ret+=stk[top].second;
        }top=0;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(sa[i]>len1);
        for(int i=1;i<=n;i++){
            while(top &&height[ stk[top].first ]>height[i])top--;top++;
            stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*height[i]+stk[top-1].second);
            if(sa[i]<len1)ret+=stk[top].second;
        }cout<<ret;
    }
}sa;
char s[maxn];
int main(){
    scanf("%s%s",s1,s2);
    len1=strlen(s1);len2=strlen(s2);
    int n=0;
    for(int i=0;i<len1;i++)s[n++]=s1[i];
    s[n++]='$';
    for(int i=0;i<len2;i++)s[n++]=s2[i];
    s[n]=0;
    sa.Sa(s,n,128);
    sa.solve(n);
    return 0;
}

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6+10;

char t[151][80];
int cnt[151];
char s[maxn];
int n;
struct trie{
    int nxt[maxn][26],fail[maxn];
    int ed[maxn];
    int rt,L;
    int newnode(){
        memset(nxt[L],-1,sizeof nxt[L]);
        ed[L++]=0;
        return L-1;
    }
    void init(){
        L=0;rt=newnode();
    }
    void insert(int id,char buf[]){
        int len=strlen(buf);
        int now=rt;
        for(int i=0;i<len;++i){
            if(nxt[now][buf[i]-'a']==-1)nxt[now][buf[i]-'a']=newnode();
            now=nxt[now][buf[i]-'a'];
        }ed[now]=id;
    }
    void build(){
        queue<int>q;
        fail[rt]=rt;
        for(int i=0;i<26;++i){
            if(nxt[rt][i]==-1)nxt[rt][i]=rt;
            else {
                fail[nxt[rt][i]]=rt;
                q.push(nxt[rt][i]);
            }
        }
        while(!q.empty()){
            int now = q.front();q.pop();
            for(int i=0;i<26;++i){
                if(nxt[now][i]==-1)nxt[now][i]=nxt[fail[now]][i];
                else{
                    fail[nxt[now][i]]=nxt[fail[now]][i];
                    q.push(nxt[now][i]);
                }
            }
        }
    }
    void query(char buf[]){
        int len=strlen(buf);
        int now = rt;
        for(int i=0;i<len;++i){
            now = nxt[now][buf[i]-'a'];
            int tmp=now;
            while(tmp!=rt){
                cnt[ed[tmp]]++;
                tmp=fail[tmp];
            }
        }
    }
}ac;
int main(){
    while(cin>>n&&n){
        ac.init();
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;++i){
            scanf("%s",t[i]);
            ac.insert(i,t[i]);
        }ac.build();
        scanf("%s",s);
        ac.query(s);
    }
    return 0;
}

SAM

最短不重复子串4合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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf  = 0x3f3f3f3f;
const int maxn = 4e3+10;
char a[maxn],b[maxn];
int lena,lenb;
struct SEM{
    int nxt[maxn][26];
    int len;
    inline void init(char *s,int l){
        len=l;
        for(int i=0;i<26;i++)nxt[len][i]=len;
        for(int i=len-1;i>=0;i--){
            memcpy(nxt[i],nxt[i+1],sizeof nxt[i+1]);
            nxt[i][s[i]-'a']=i;
        }
    }
}AA,BB;
struct SAM{
    int pa[maxn<<1],son[maxn<<1][27];
    int deep[maxn<<1],cnt,root,last;
    inline int newnode(int _deep){
        deep[++cnt]=_deep;
        return cnt;
    }
    inline void sam(int alp){
        int np=newnode(deep[last]+1);
        int u=last;
        memset(son[np],0,sizeof son[np]);
        while(u&&!son[u][alp])son[u][alp]=np,u=pa[u];
        if(!u)pa[np]=root;
        else{
            int v=son[u][alp];
            if(deep[v]==deep[u]+1)pa[np]=v;
            else{
                int nv=newnode(deep[u]+1);
                memcpy(son[nv],son[v],sizeof son[v]);
                pa[nv]=pa[v],pa[v]=pa[np]=nv;
                while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u];
            }
        }last=np;
    }
    inline void pre(){
        cnt=0;
        memset(son[1],0,sizeof son[1]);
        root=last=newnode(0);
    }
}A,B;
int solve1(){
    int ret=inf;
    for(int i=0;i<lena;i++){
        int pos=B.root;
        for(int j=i;j<lena;j++){
            if(B.son[pos][a[j]-'a'])pos=B.son[pos][a[j]-'a'];
            else{
                ret=min(ret,j-i+1);break;
            }
        }
    }return ret==inf?-1:ret;
}
int solve2(){
    int ret=inf;
    for(int i=0;i<lena;i++){
        int pos=0;
        for(int j=i;j<lena;j++){
            if(BB.nxt[pos][a[j]-'a']==BB.len){
                ret=min(ret,j-i+1);break;
            } else pos=BB.nxt[pos][a[j]-'a']+1;
        }
    }return ret==inf?-1:ret;
}
int solve3(){
    int ret=inf;
    int dp[maxn];//dp[i]表示状态i能够接受的最短A的子序列
    memset(dp,0x3f,sizeof dp);
    dp[1]=0;
    for(int i=0;i<lena;i++){
        for(int j=B.root;j<=B.cnt;j++){
            if(B.son[j][a[i]-'a']){
                dp[B.son[j][a[i]-'a']]=min(dp[B.son[j][a[i]-'a']],dp[j]+1);
            } else ret=min(ret,dp[j]+1);
        }
    }return ret==inf?-1:ret;
}
struct node{
    int a,b,step;
    node(int a=0,int b=0,int step=0):a(a),b(b),step(step){}
};
bool vis[maxn][maxn]={0};
int solve4(){
    queue<node> q;
    q.push(node(0,0,0));
    while(!q.empty()){
        node now=q.front();q.pop();
        //cout<<now.a<<" "<<now.b<<" "<<now.step<<endl;
        for(int i=0;i<26;i++){
            if(AA.nxt[now.a][i]==AA.len)continue;
            if(vis[AA.nxt[now.a][i]][BB.nxt[now.b][i]])continue;
            if(BB.nxt[now.b][i]==BB.len)return now.step+1;
            vis[AA.nxt[now.a][i]][BB.nxt[now.b][i]]=1;
            q.push(node(AA.nxt[now.a][i]+1,BB.nxt[now.b][i]+1,now.step+1));
        }
    }return -1;
}
int main(){
    scanf("%s%s",a,b);
    lena=strlen(a);
    lenb=strlen(b);
    A.pre();B.pre();
    for(int i=0;i<lena;i++)A.sam(a[i]-'a');
    for(int i=0;i<lenb;i++)B.sam(b[i]-'a');
    AA.init(a,lena);BB.init(b,lenb);
    printf("%d\n",solve1());
    printf("%d\n",solve2());
    printf("%d\n",solve3());
    printf("%d\n",solve4());
    return 0;
}

允许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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int tran(char c){
    if(c=='A')return 0;if(c=='T')return 1;if(c=='C')return 2;if(c=='G')return 3;
}
char s1[maxn],s2[maxn];
int len1,len2;
struct SAM{
    int pa[maxn<<1],son[maxn<<1][4];
    int deep[maxn<<1],cnt,root,last;
    int sum[maxn<<1],topo[maxn<<1];
    int r[maxn<<1];
    inline void pre(){
        memset(r,0,sizeof r);
    }
    inline void toposort(){
        int tmp=root;
        for(int a=0;a<len1;a++){
            tmp=son[tmp][tran(s1[a])];
            r[tmp]=1;
        }
        memset(sum,0,sizeof sum);
        for(int a=1;a<=cnt;a++)sum[deep[a]]++;
        for(int a=1;a<=deep[last];a++)sum[a]+=sum[a-1];
        for(int a=1;a<=cnt;a++)topo[sum[deep[a]]--]=a;
        for(int a=cnt;a>=1;a--)r[pa[topo[a]]] += r[topo[a]];
    }
}A;
int ans;
void dfs(int pos1,int pos2,int lim){
    if(lim>3)return;
    if(pos2==len2){
        ans+=A.r[pos1];return;
    }
    for(int a=0;a<4;a++){
        if(A.son[pos1][a]){
            dfs(A.son[pos1][a],pos2+1,lim+(a!=tran(s2[pos2])));
        }
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        ans=0;
        scanf("%s%s",s1,s2);
        A.pre();
        len1=strlen(s1);len2=strlen(s2);
        for(int i=0;i<len1;i++)A.sam(tran(s1[i]));
        A.toposort();
        dfs(1,0,0);
        printf("%d\n",ans);
    }
    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
/**T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+1000;
char s[maxn];
int pa[maxn<<1],son[maxn<<1][27];
int deep[maxn<<1],cnt,root,last;
int sum[maxn<<1],topo[maxn<<1];
int r[maxn<<1],rr[maxn<<1];
inline void sam(int alp){
    r[np]=1;
}
inline void toposort(){
    for(int a=1;a<=cnt;a++)sum[deep[a]]++;
    for(int a=1;a<=deep[last];a++)sum[a]+=sum[a-1];
    for(int a=1;a<=cnt;a++)topo[sum[deep[a]]--]=a;
}
int T,K;
int main(){
    scanf("%s%d%d",s,&T,&K);
    pre();
    memset(son[1],0,sizeof son[1]);
    int len=strlen(s);
    for(int a=0;a<len;a++){
        sam(s[a]-'a');
    }
    toposort();
    for(int i=cnt;i;i--){
        if(T)r[pa[topo[i]]] += r[topo[i]];
        else r[topo[i]]=1;
    }
    r[root]=0;
    for(int i=cnt;i;i--){
        rr[topo[i]]=r[topo[i]];
        for(int j=0;j<26;j++){
            rr[topo[i]]+=rr[son[topo[i]][j]];
        }
    }
    int now=root;
    if(K>rr[root])return puts("-1");
    while(K){
        K-=r[now];
        if(K<=0)break;
        for(int i=0;i<26;i++){
            if(son[now][i]){
                if(rr[son[now][i]]>=K){
                    putchar(i+'a');
                    now=son[now][i];
                    break;
                }
                else K-=rr[son[now][i]];
            }
        }
    }
    puts("");
    return 0;
}

出现次数在[A,B]之间的子串个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int tmp=root;
for(int a=0;a<len;a++){
    tmp=son[tmp][s[a]-'A'];
    r[tmp]=1;
}
/**将所有状态的right集合大小赋值为1**/
for(int a=cnt;a>=1;a--)r[pa[topo[a]]] += r[topo[a]];
long long ans=0;
for(int a=cnt;a>=1;a--){
    if(r[topo[a]]>=A && r[topo[a]]<=B){
        ans+=deep[topo[a]] - deep[pa[topo[a]]];
        /**right集合中不同子串个数为deep[p] - deep[pa[p]]]**/
    }
}
cout<<ans<<endl;

两串LCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int a=0;a<len;a++)sam(s[a]-'a');
for(int a=1,l=0,p=1;a<=m;a++){
    int x=t[a]-'a';
    if(son[p][x])p=son[p][x],l++;
    else{
        for(;p&&!son[p][x];p=pa[p]);
        if(!p)l=0,p=1;
        else l=deep[p]+1,p=son[p][x];
    }
    /**
    p表示当前在哪个状态，l表示当前状态匹配的最长子串
    deep[p]表示在p状态下，得到的最长子串的长度
    **/
    ans=max(ans,l);
}
printf("%d\n",ans);

多个串的LCS

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
char s[maxn];
int pa[maxn<<1],son[maxn<<1][27];
int deep[maxn<<1],cnt,root,last;
int sum[maxn<<1],topo[maxn<<1];
int arr[maxn<<1],ned[maxn<<1];
inline int newnode(int _deep){
    deep[++cnt]=_deep;
    return cnt;
}
inline void sam(int alp){
}
inline void toposort(){
    for(int a=1;a<=cnt;a++)sum[deep[a]]++;
    for(int a=1;a<=deep[last];a++)sum[a]+=sum[a-1];
    for(int a=1;a<=cnt;a++)topo[sum[deep[a]]--]=a;
}
inline void pre(){
    root=last=newnode(0);
}
int main(){
    scanf("%s",s);
    pre();
    memset(son[1],0,sizeof son[1]);
    int len=strlen(s);
    for(int a=0;a<len;a++)sam(s[a]-'a');
    toposort();
    for(int a=1;a<=cnt;a++)ned[a]=deep[a];
    while(scanf("%s",s+1)!=EOF){
        int m=strlen(s+1);
        for(int a=1,l=0,p=1;a<=m;a++){
            int x=s[a]-'a';
            if(son[p][x])p=son[p][x],l++;
            else{
                for(;p && !son[p][x];p=pa[p]);
                if(!p)l=0,p=1;
                else l=deep[p]+1,p=son[p][x];
            }
            arr[p]=max(arr[p],l);
        }
        for(int a=cnt;a>=1;a--){
            int p=topo[a];
            ned[p]=min(ned[p],arr[p]);
            if(arr[p]&&pa[p])arr[pa[p]]=deep[pa[p]];
            arr[p]=0;
        }
    }
    int ans=0;
    for(int a=1;a<=cnt;a++)ans=max(ans,ned[a]);
    printf("%d\n",ans);
    return 0;
}

区间[L,R]内不同子串个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline void sam(int alp){
    tot+=deep[np]-deep[pa[np]];
}
inline void pre(){
    cnt=0;
    memset(son[1],0,sizeof son[1]);
    root=last=newnode(0);
    tot=0;
}
for(int i=0;i<len;i++){
    pre();
    for(int j=i;j<len;j++){
        sam(s[j]-'a');
        ans[i][j]=tot;
    }
}
int q;scanf("%d",&q);
while(q--){
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",ans[l-1][r-1]);
}

统计长度为[1..l]的子串最多出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int tmp=root;
for(int a=0;a<len;a++){
    tmp=son[tmp][s[a]-'a'];
    r[tmp]=1;
}
/***将原串前缀状态的right集合大小设为1，
相当于在后缀树中将后缀结点标记为1**/
toposort();
/**deep[a] > deep[pa[a]]，所以排序，
用a状态更新pa[a]的状态，只考虑结点的deep便可
**/
for(int a=cnt;a>=1;a--)r[pa[topo[a]]] += r[topo[a]];/**right表示状态在整个串出现次数**/
for(int a=1;a<=cnt;a++)f[deep[a]] = max(f[deep[a]] , r[a]);/**只更新最长串**/
for(int a=len;a>=1;a--)f[a-1]=max(f[a],f[a-1]);/**长串更新短串：短串包含在长串里面**/
for(int i=1;i<=len;i++)printf("%d\n",f[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
int minpre(char s[]){
	int m = strlen(s);
	memcpy(s + m, s,m*sizeof(char));
	int i = 0,j = 1;//i表示从i往后是有可能的，j表示下一个试探的位置 
	while(j < m && i < m) {
		int k;
		for (k = 0;s[i + k] == s[j + k] && k < m; k++)
		if(k == m ) return min(i,j);//如果相等了，那最小的就是答案 
		if(s[i + k] > s[j + k]) i = i + k + 1;//i到i+k开始的都不可能 
		else (j = j + k + 1);//同上 
	    if (i == j) j++;//刚好相等，重新比较 
	    
	}
	if(i < m) return i;
	else return j;
}
int main(){
    char s[20005];
	int n;
	scanf("%d",&n);
	while(n--){
		scanf("%s",s);
	    printf("%d\n",minpre(s) + 1);
	}	
}
赏

谢谢打赏

支付宝
微信
置顶

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

iOS Developer, ACMer, ...