ACM模板

发表于 | 分类于

AC自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxnode=11000;
const int sigma_size=26;
struct AC_Automata
{
    int ch[maxnode][sigma_size];
    int val[maxnode];   // 每个字符串的结尾结点都有一个非0的val
    int f[maxnode];     // fail函数
    int last[maxnode];  // last[i]=j表j节点表示的单词是i节点单词的后缀，且j节点是单词节点
    int sz;
    //初始化0号根节点的相关信息
    void init()
    {
        sz=1;
        memset(ch[0],0,sizeof(ch[0]));
        val[0]=0;
    }
    //insert负责构造ch与val数组
    //插入字符串,v必须非0表示一个单词节点
    void insert(char *s,int v)
    {
        int n=strlen(s),u=0;
        for(int i=0; i<n; i++)
        {
            int id=s[i]-'a';
            if(ch[u][id]==0)
            {
                ch[u][id]=sz;
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz++]=0;
            }
            u=ch[u][id];
        }
        val[u]=v;
    }
    //getFail函数负责构造f和last数组
    void getFail()
    {
        queue<int> q;
        last[0]=f[0]=0;
        for(int i=0; i<sigma_size; i++)
        {
            int u=ch[0][i];
            if(u)
            {
                f[u]=last[u]=0;
                q.push(u);
            }
        }
        while(!q.empty())// 按BFS顺序计算fail
        {
            int r=q.front(); q.pop();
            for(int i=0; i<sigma_size; i++)
            {
                int u=ch[r][i];
                if(u==0)continue;
                q.push(u);
                int v=f[r];
                while(v && ch[v][i]==0) v=f[v];
                f[u]= ch[v][i];
                last[u] =  val[f[u]]?f[u]:last[f[u]];
            }
        }
    }
    //递归打印与结点i后缀相同的前缀节点编号
    //进入此函数前需保证val[i]>0
    void print(int i)
    {
        if(i)
        {
            printf("%d\n",i);
            print(last[i]);
        }
    }
    // 在s中找出 出现了哪几个模板单词
    void find(char *s)
    {
        int n=strlen(s),j=0;
        for(int i=0; i<n; i++)
        {
            int id=s[i]-'a';
            while(j && ch[j][id]==0) j=f[j];
            j=ch[j][id];
            if(val[j]) print(j);
            else if(last[j]) print(last[j]);
        }
    }
};
AC_Automata ac;

CDQ分治

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
/*
平面上有N个点，每个点的横纵坐标在[0,1e7]之间，有M个询问，每个询问为查询在指定矩形之内有多少个点，
矩形用(x1,y1,x2,y2)的方式给出，其中(x1,y1)为左下角坐标，(x2,y2)为右上角坐标。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
using namespace std;
const int MAXN = 500001; // 点的数量
const int MAXM = 500001; // 询问数量
const int MAXQ = MAXN+(MAXM<<2);
const int MAXL = 10000002; // 树状数组大小
int n, m, maxy = -1;
namespace IO { // 快读相关
    const int BUFSZ = 1e7;
    char buf[BUFSZ]; int idx, end;
    void init() { idx = BUFSZ; }
    char getch() {
        if( idx == BUFSZ ) {
            end = fread( buf, 1, BUFSZ, stdin ); idx = 0;
        }
        if( idx == end ) return EOF;
        return buf[idx++];
    }
    int getint() {
        int num = 0; char ch;
        while( isspace(ch=getch()) );
        do { num = num*10 + ch-'0'; } while( isdigit(ch=getch()) );
        return num;
    }
}
using IO::getint;
struct Query {
    int type, x, y, w, aid; // w表示对查询结果贡献(+还是-)，aid是“第几个查询”
    bool operator<( const Query &rhs ) const {
        return x == rhs.x ? type < rhs.type : x < rhs.x;
    }
}query[MAXQ];
int qidx = 0;
void addq( int type, int x, int y, int w, int aid ) {
    query[qidx++] = (Query){type,x,y,w,aid};
}
int ans[MAXM], aidx = 0;
namespace BIT { // 树状数组相关
    int arr[MAXL];
    inline int lowbit( int num ) { return num&(-num); }
    void add( int idx, int val ) {
        while( idx <= maxy ) {
            arr[idx] += val;
            idx += lowbit(idx);
        }
    }
    int query( int idx ) {
        int ans = 0;
        while( idx ) {
            ans += arr[idx];
            idx -= lowbit(idx);
        }
        return ans;
    }
    void clear( int idx ){
        while( idx <= maxy ) {
            if( arr[idx] ) arr[idx] = 0; else break;
            idx += lowbit(idx);
        }
    }
}
Query tmp[MAXQ];
void cdq( int L, int R ) {
    if( R-L <= 1 ) return;
    int M = (L+R)>>1; cdq(L,M); cdq(M,R);
    int p = L, q = M, o = L;
    while( p < M && q < R ) {
        if( query[p] < query[q] ) {
            if( query[p].type == 0 ) BIT::add( query[p].y, 1 );
            tmp[o++] = query[p++];
        } else {
            if( query[q].type == 1 ) ans[query[q].aid] += query[q].w * BIT::query( query[q].y );
            tmp[o++] = query[q++];
        }
    }
    while( p < M ) tmp[o++] = query[p++];
    while( q < R ) {
        if( query[q].type == 1 ) ans[query[q].aid] += query[q].w * BIT::query( query[q].y );
        tmp[o++] = query[q++];
    }
    for( int i = L; i < R; ++i ) {
        BIT::clear( tmp[i].y ); // 清空树状数组
        query[i] = tmp[i];
    }
}
int main() {
    IO::init(); n = getint(); m = getint();
    while( n-- ) {
        int x,y; x = getint(); y = getint(); ++x; ++y; // 为了方便，把坐标转化为[1,1e7+1]
        addq(0,x,y,0,0); maxy = max( maxy, y ); // 修改操作无附加信息
    }
    while( m-- ) {
        int x1,y1,x2,y2; x1 = getint(); y1 = getint(); x2 = getint(); y2 = getint(); ++x1; ++y1; ++x2; ++y2;
        addq(1,x1-1,y1-1,1,aidx); addq(1,x1-1,y2,-1,aidx); addq(1,x2,y1-1,-1,aidx); addq(1,x2,y2,1,aidx); ++aidx;
        maxy = max( maxy, max(y1,y2) );
    }
    cdq(0,qidx);
    for( int i = 0; i < aidx; ++i ) printf( "%d\n", ans[i] );
    return 0;
}

CDQ分治+斜率dp

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
/*
dp[i]=min{dp[j]+(S+T[i]-T[j])*F[i]};
dp[j]=F[i]*T[j]+dp[i]-(S+T[i])*F[i];
令y=dp[j],x=T[j],k=F[i];
则要让dp[i]最小，则斜率为k的直线切y轴最小
维护下凸包
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 300010
int t[maxn],f[maxn],st[maxn],S;
ll T[maxn],F[maxn],ans[maxn];
struct query {
    int p,x;
    ll y,k;
    query() {
        y=1e18;
    }
    query(int p,int x,ll y,ll k):p(p),x(x),y(y),k(k) {}
} q[maxn],q1[maxn],q2[maxn];
double getk(int i,int j) {
    if(q[i].x==q[j].x&&q[i].y<q[j].y) return -1e18;
    else if(q[i].x==q[j].x) return 1e18;
    return 1.0*(q[i].y-q[j].y)/(q[i].x-q[j].x);
}
void cdq(int L,int R) {
    if(L>R) return;
    if(L==R) {
        ans[q[L].p]=q[L].y;
        return;
    }
    int M=(L+R)/2;
    int a=0,b=0;
    for(int i=L; i<=R; i++) {
        if(q[i].p<=M) q1[a++]=q[i];
        else q2[b++]=q[i];
    }
    for(int i=L; i<L+a; i++) q[i]=q1[i-L];
    for(int i=L+a; i<=R; i++) q[i]=q2[i-L-a];
    cdq(L,M);
    int top=0;
    for(int i=L; i<=M; i++) {
        while(top>1&&getk(i,st[top-1])<=getk(st[top-1],st[top-2])) top--;
        st[top++]=i;
    }
    int j=0;
    for(int i=M+1; i<=R; i++) {
        while(j<top-1&&(double)q[i].k>getk(st[j+1],st[j])) j++;
        int k=st[j];
        q[i].y=min(q[i].y,q[k].y+(S+T[q[i].p]-T[q[k].p])*F[q[i].p]);
//        printf("%d %d %d %lld\n",L,R,j,q[i].y);
    }
    cdq(M+1,R);
    a=L;
    b=M+1;
    int o=0;
    while(a<=M&&b<=R) {
        if(q[a].x<q[b].x) q1[o++]=q[a++];
        else q1[o++]=q[b++];
    }
    while(a<=M) q1[o++]=q[a++];
    while(b<=R) q1[o++]=q[b++];
    for(int i=L; i<=R; i++) {
        q[i]=q1[i-L];
//        printf("**%d\n",q[i].x);
    }
}
bool cmp(const query &a,const query &b) {
    return a.k<b.k;
}
int main() {
//    freopen("data.txt","r",stdin);
//    freopen("ans.txt","w",stdout);
    int n;
    scanf("%d%d",&n,&S);
    for(int i=1; i<=n; i++)
        scanf("%d%d",&t[i],&f[i]);
    q[0]=query(0,0,0,0);
    for(int i=1; i<=n+10; i++) q[i].y=1e18;
    for(int i=1; i<=n; i++) {
        T[i]=T[i-1]+t[n-i+1];
        F[i]=F[i-1]+(ll)f[n-i+1];
        q[i].p=i;
        q[i].x=T[i];
        q[i].k=F[i];
    }
//    sort(q,q+n+1,cmp);
    cdq(0,n);
//    for(int i=0;i<=n;i++)
    printf("%lld\n",ans[n]);
    return 0;
}
/*
5 1
0 2
2 2
1 2
0 2
-2 2
*/

LCA

RMQ法

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 maxn 100010
struct node{
    int to,cost;
};
vector<node> g[maxn];
int ver[2*maxn],id[2*maxn],first[maxn];
int dis[maxn];;
//  ver[i] : i 对应的节点编号
//  id[i] :  i 对应节点深度
int tot,n,q;
int dp[2*maxn][30];
void dfs(int root,int dep,int s,int fa){
    ver[++tot]=root;id[tot]=dep;first[root]=tot;dis[root]=s;
    for(int i=0;i<g[root].size();i++){
        int v=g[root][i].to,w=g[root][i].cost;
        if(v==fa) continue;
        dfs(v,dep+1,s+w,root);
        ver[++tot]=root;id[tot]=dep;
    }
}
void ST(){
    for(int i=1;i<=tot;i++)
        dp[i][0]=i;
    for(int j=1;(1<<j)<=tot;j++){
        for(int i=1;i+(1<<j)-1<=tot;i++){
            int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
            dp[i][j]=id[a]<id[b]?a:b;
        }
    }
}
int RMQ(int le,int ri){
    le=first[le],ri=first[ri];
    if(le>ri) swap(le,ri);
    int k=0;
    while((1<<(k+1))<=ri-le+1) k++;
    int a=dp[le][k],b=dp[ri-(1<<k)+1][k];
    return id[a]<id[b]?ver[a]:ver[b];
}
int main(){
    int ca,kase=0;
    scanf("%d",&ca);
    while(ca--){
        for(int i=0;i<maxn;i++) g[i].clear();
        scanf("%d%d",&n,&q);
        int u,v,w;
        for(int i=0;i<n-1;i++){
            scanf("%d%d%d",&u,&v,&w);
            g[u].push_back((node){v,w});
            g[v].push_back((node){u,w});
        }
        tot=0;dfs(1,1,0,-1);
        ST();
        
    }
    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
1. DFS预处理出所有节点的深度和父节点
inline void dfs(int u) {
    int i;
    for(i=head[u]; i!=-1; i=next[i]) {
        if (!deep[to[i]]) {
            deep[to[i]] = deep[u]+1;
            p[to[i]][0] = u; //p[x][0]保存x的父节点为u;
            dfs(to[i]);
        }
    }
}
2. 初始各个点的2^j祖先是谁 ,其中 2^j (j =0...log(该点深度))倍祖先，1倍祖先就是父亲，2倍祖先是父亲的父亲......。
void init() {
    int i,j;
    //p[i][j]表示i结点的第2^j祖先
    for(j=1; (1<<j)<=n; j++)
        for(i=1; i<=n; i++)
            if(p[i][j-1]!=-1)
                p[i][j]=p[p[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先
}
3.从深度大的节点上升至深度小的节点同层，如果此时两节点相同直接返回此节点，即lca。
否则，利用倍增法找到最小深度的 p[a][j]!=p[b][j]，此时他们的父亲p[a][0]即lca。
int lca(int a,int b) { //最近公共祖先
    int i,j;
    if(deep[a]<deep[b])swap(a,b);
    for(i=0; (1<<i)<=deep[a]; i++);
    i--;
    //使a，b两点的深度相同
    for(j=i; j>=0; j--)
        if(deep[a]-(1<<j)>=deep[b])
            a=p[a][j];
    if(a==b)return a;
    //倍增法，每次向上进深度2^j，找到最近公共祖先的子结点
    for(j=i; j>=0; j--) {
        if(p[a][j]!=-1&&p[a][j]!=p[b][j]) {
            a=p[a][j];
            b=p[b][j];
        }
    }
    return p[a][0];
}

Manacher

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
//给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=110010;
char Ma[MAXN*2];
int Mp[MAXN*2];
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;
        }
    }
}
char s[MAXN];
int main() {
    while(scanf("%s",s)==1) {
        int len=strlen(s);
        Manacher(s,len);
        int ans=0;
        for(int i=0; i<2*len+2; i++)
            ans=max(ans,Mp[i]-1);
        printf("%d\n",ans);
    }
    return 0;
}

SBTree

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
 #include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 10005;
const int INF=0x7FFFFFFF;
const int ERROR=-0x3f3f3f3f;
struct SBT {
    int key,left,right,size;
    SBT() {
        key=left=right=size=0;
    }
} tree[N];
int root,top;
void left_rot(int &x) {
    int y = tree[x].right;
    tree[x].right = tree[y].left;
    tree[y].left = x;
    tree[y].size = tree[x].size;//转上去的节点数量为先前此处节点的size
    tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
    x = y;
}
void right_rot(int &x) {
    int y = tree[x].left;
    tree[x].left = tree[y].right;
    tree[y].right = x;
    tree[y].size = tree[x].size;
    tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
    x = y;
}
void maintain(int &x,bool flag) {
    if(flag == false) { //左边
        if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)//左孩子的左子树大于右孩子
            right_rot(x);
        else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size) { //右孩子的右子树大于右孩子
            left_rot(tree[x].left);
            right_rot(x);
        } else return;
    } else { //右边
        if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)//右孩子的右子树大于左孩子
            left_rot(x);
        else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size) { //右孩子的左子树大于左孩子
            right_rot(tree[x].right);
            left_rot(x);
        } else return;
    }
    maintain(tree[x].left,false);
    maintain(tree[x].right,true);
    maintain(x,true);
    maintain(x,false);
}
/*
*insert没有合并相同的元素，如果出现相同的元素则把它放到右子树上，这样能保证求第k小数的时候对相同元素也能正确
*/
void insert(int &x,int key) {
    if(x == 0) {
        x = ++top;
        tree[x].left = tree[x].right = 0;
        tree[x].size = 1;
        tree[x].key = key;
    } else {
        tree[x].size ++;
        if(key < tree[x].key) insert(tree[x].left,key);
        else  insert(tree[x].right,key);//相同元素插入到右子树中
        maintain(x, key >= tree[x].key);//每次插入把平衡操作压入栈中
    }
}
int erase(int &x,int key) {//删除之前判断是否存在该元素
    int d_key;
//    if(!x) return 0;
    tree[x].size --;
    if((key == tree[x].key)||(key < tree[x].key && tree[x].left == 0) ||
            (key>tree[x].key && tree[x].right == 0)) {
        d_key = tree[x].key;
        if(tree[x].left && tree[x].right) {
            tree[x].key = erase(tree[x].left,tree[x].key+1);
        } else {
            x = tree[x].left + tree[x].right;
        }
    } else if(key > tree[x].key)
        d_key = erase(tree[x].right,key);
    else if(key < tree[x].key)
        d_key = erase(tree[x].left,key);
    return d_key;
}
int getmin() {
    int x;
    for(x = root ; tree[x].left; x = tree[x].left);
    return tree[x].key;
}
int getmax() {
    int x;
    for(x = root ; tree[x].right; x = tree[x].right);
    return tree[x].key;
}
int Kth(int &x,int k) { //求第k小数,有重复元素也不会出错
    if(x==0||k<=0||k>tree[x].size) return ERROR;
    int r = tree[tree[x].left].size + 1;
    if(r == k) return tree[x].key;
    else if(r < k) return Kth(tree[x].right,k - r);
    else return Kth(tree[x].left,k);
}
int Rank(int &x,int key) { //求key排第几,返回值范围在[1,num+1]范围内
    if(!x) return 1;
    if(key <= tree[x].key)
        return Rank(tree[x].left,key);
    else return Rank(tree[x].right,key) + tree[tree[x].left].size + 1;
}
int pred(int &x,int y,int key) { //前驱的下标 小于
    if(x == 0) return y;
    if(tree[x].key < key)
        return pred(tree[x].right,x,key);
    else return pred(tree[x].left,y,key);
}
int succ(int &x,int y,int key) { //后继的下标 大于
    if(x == 0) return y;
    if(tree[x].key > key)
        return succ(tree[x].left,x,key);
    else return succ(tree[x].right,y,key);
}
void inorder(int &x) {
    if(x==0) return;
    else {
        inorder(tree[x].left);
        cout<<x<<" "<<tree[x].key<<" "<<" "<<tree[x].size<<" "<<tree[tree[x].left].key<<" "<<tree[tree[x].right].key<<endl;
        inorder(tree[x].right);
    }
}
bool find(int &x,int key) {
    while(x) {
        if(key==tree[x].key) return true; //存在
        if(key<tree[x].key) x=tree[x].left;
        else x=tree[x].right;
    }
    return false;              //不存在
}
int count(int &x,int key){
    return Rank(x,key+1)-Rank(x,key);
}
int main() {
    root = top = 0;
    char ch;
    int x,tmp;
    while(scanf("%c %d",&ch,&x)) {
        switch(ch) {
        case 'I':
            insert(root,x);
            break;
        case 'D':
            erase(root,x);
            break;
        case 'K':
            tmp=Kth(root,x);
            printf("%d\n",tmp);
            break;
        case 'R':
            printf("%d\n",Rank(root,x));
            break;
        case 'P':
            tmp = pred(root,0,x);
            printf("%d\n",tree[tmp].key);
            break;
        case 'S':
            tmp = succ(root,0,x);
            printf("%d\n",tree[tmp].key);
            break;
        case 'L':
            inorder(root);
            break;
        case 'C':
            printf("%d\n",count(root,x));
            break;
        }
    }
    return 0;
}

splay

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
 #include<bits/stdc++.h>
typedef long long  ll;
using namespace std;
#define maxn 100010
int a[maxn];
struct Node {
    Node* ch[2];
    Node* par;
    int rank;// 当前节点在序列中的位置
    int s;// 节点总数
    int flip;// 旋转标记
    int add;// 增减标记
    int val;// 节点的值
    int sum;
    Node() {
        par=NULL;
        rank=1;
        s=1;
        flip=0;
        add=0;
        sum=0;
        ch[0]=ch[1]=NULL;
    }
    int cmp(int x) const {
        if (x==rank) return -1;
        return x<rank? 0 : 1;
    }
    void maintain(){
        s=1;
        rank=1;
        sum=val;
        if (ch[0]!=NULL) {
            s+=ch[0]->s;
            rank+=ch[0]->s;
            sum+=ch[0]->sum;
        }
        if (ch[1]!=NULL) {
            s+=ch[1]->s;
            sum+=ch[1]->sum;
        }
    }
    void pushdown(){
        if (flip) {
            flip=0;
            if(ch[0]!=NULL) {
                ch[0]->flip^=1;
                swap(ch[0]->ch[0],ch[0]->ch[1]);
            }
            if(ch[1]!=NULL) {
                ch[1]->flip^=1;
                swap(ch[1]->ch[0],ch[1]->ch[1]);
            }
        }
        if (add) {
            if (ch[0]!=NULL) {
                ch[0]->val+=add;
                ch[0]->add+=add;
                ch[0]->sum+=add*ch[0]->s;
            }
            if (ch[1]!=NULL) {
                ch[1]->val+=add;
                ch[1]->add+=add;
                ch[1]->sum+=add*ch[1]->s;
            }
            add=0;
        }
    }
};
Node* root=NULL;
void rotate(Node* &o,int d) {
    Node* k = o->ch[d^1];
    Node* par = o->par;
    o->ch[d^1] = k->ch[d];
    if(k->ch[d]) k->ch[d]->par=o;
    k->ch[d] = o;
    o->par=k;
    k->par=par;
    o->maintain();
    k->maintain();
    o=k;
}
void splay(Node* &o,int k) {
    //correct
    o->pushdown();
    o->maintain();
    int d= o->cmp(k);
    if (d==1) k -= o->rank;
    if (d!=-1) {
        Node* p = o->ch[d];
        p->pushdown();
        p->maintain();
        int d2 = p->cmp(k);
        int k2 = (d2==0 ? k : k-p->rank);
        if (d2!=-1) {
            splay(p->ch[d2],k2);
            if (d==d2) rotate(o,d^1);
            else rotate(o->ch[d], d);
        }
        rotate(o,d^1);
    }
}
int Rank(Node *o){
    int cnt=o->rank;
    while(o->par){
        if(o->par->ch[1]==o) cnt+=o->par->rank;
        o=o->par;
    }
    return cnt-1;
}
//Node* id[maxn];
Node* build(int l,int r,Node *fa) {
    Node* p;
    int mid=(l+r)>>1;
    p=new Node();
    p->val=a[mid];
    //id[a[mid]]=p;
    p->s=r-l+1;
    p->rank=mid-l+1;
    p->flip=0;
    p->add=0;
    p->par=fa;
    p->ch[0]=p->ch[1]=NULL;
    if (mid-1>=l) p->ch[0]=build(l,mid-1,p);
    if (mid+1<=r) p->ch[1]=build(mid+1,r,p);
    p->maintain();
    return p;
}
void remove(Node* &o){
    if(o==NULL) return;
    remove(o->ch[0]);remove(o->ch[1]);
    delete o;
    o=NULL;
}
int flag;
vector<int> vec;
void InOrder(Node* o) {
    o->pushdown();
    o->maintain();
    if (o->ch[0]!=NULL) InOrder(o->ch[0]);
    vec.push_back(o->val);
    if (o->ch[1]!=NULL) InOrder(o->ch[1]);
}
void print(){
    vec.clear();
    InOrder(root);
    for(int i=1;i<vec.size();i++)
        printf("%d%c",vec[i],i==vec.size()-1?'\n':' ');
}
// 分裂
void split(Node* o,int k,Node* &left,Node* &right) {
    splay(o,k);
    left=o;
    right=o->ch[1];
    if(right) right->par=NULL;
    o->ch[1]=NULL;
    left->maintain();
}
// 合并
Node* merge(Node* left,Node* right) {
    splay(left, left->s);
    left->ch[1]=right;
    if(right) right->par=left;
    left->maintain();
    return left;
}
void update(int l,int r,int val) {
    Node *left,*mid,*right,*o;
    split(root,l,left,o);
    split(o,r-l+1,mid,right);
    mid->add+=val;
    mid->val+=val;
    mid->pushdown();
    mid->maintain();
    root=merge(merge(left,mid),right);
}
void reverse(int l,int r) {
    Node *left,*mid,*right,*o;
    split(root,l,left,o);
    split(o,r-l+1,mid,right);
    mid->flip^=1;
    swap(mid->ch[1],mid->ch[0]);
    mid->pushdown();mid->maintain();
    root=merge(merge(left,mid),right);
}
int query(int l,int r) {
    Node *left,*mid,*right,*o;
    split(root,l,left,o);
    split(o,r-l+1,mid,right);
    int ret=mid->sum;
    root=merge(merge(left,mid),right);
    return ret;
}
void revolve(int l,int r,int t){//[l,r]区间右移t位，r变为l，l变为l+1...
    int len=r-l+1;
    t%=len;
    if(!t) return;
    Node *left,*mid,*right,*o;
    split(root,l,left,o);
    split(o,len,mid,right);
    Node *le,*ri;
    split(mid,len-t,le,ri);
    root=merge(merge(left,merge(ri,le)),right);
}
void addPoint(int pos,int n){
    Node *mid=build(1,n,NULL);
    Node *left,*right;
    split(root,pos,left,right);
    root=merge(merge(left,mid),right);
}
void delPoint(int pos,int n){
    Node *left,*mid,*right,*o;
    split(root,pos,left,o);
    split(o,n,mid,right);
    remove(mid);
    root=merge(left,right);
}
int main(int argc, char const *argv[]) {
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF){
        remove(root);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        root=build(0,n,NULL);
        char op[15];
        while(q--){
            scanf("%s",op);
            if(op[0]=='A'){
                int l,r,v;
                scanf("%d%d%d",&l,&r,&v);
                update(l,r,v);
            }else if(op[0]=='R'){
                int l,r;
                scanf("%d%d",&l,&r);
                reverse(l,r);
            }else if(op[0]=='Q'){
                int l,r;
                scanf("%d%d",&l,&r);
                printf("%d\n",query(l,r));
            }else if(op[0]=='I'){
                int pos,k;
                scanf("%d%d",&pos,&k);
                for(int i=1;i<=k;i++)
                    scanf("%d",&a[i]);
                addPoint(pos,k);
            }else if(op[0]=='D'){
                int pos,k;
                scanf("%d%d",&pos,&k);
                delPoint(pos,k);
            }else{
                print();
            }
        }
    }
    return 0;
}
/*
6 100
5 1 -1 7 5 0
*/

splay修改区间为定值

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
  #include<bits/stdc++.h>
typedef long long  ll;
using namespace std;
#define ini -1111
#define maxn 1000010
int a[maxn];
struct Node {
    Node* ch[2];
    Node* par;
    int rank;// 当前节点在序列中的位置
    int s;// 节点总数
    int flip;// 旋转标记
    int setv;// 增减标记
    int val;// 节点的值
    int sum;
    int ma,lv,rv;
    Node() {
        par=NULL;
        rank=1;
        s=1;
        flip=0;
        setv=ini;
        sum=0;
        ma=lv=rv=0;
        ch[0]=ch[1]=NULL;
    }
    int cmp(int x) const {
        if (x==rank) return -1;
        return x<rank? 0 : 1;
    }
    void maintain() {
        s=1;
        rank=1;
        sum=val;
        int m=val;
        ma=lv=rv=val;
        if (ch[0]!=NULL) {
            s+=ch[0]->s;
            rank+=ch[0]->s;
            sum+=ch[0]->sum;
            m=max(m,ch[0]->rv+m);
            ma=max(m,ch[0]->ma);
            lv=max(ch[0]->lv,sum);
            if(ch[1]==NULL) rv=max(rv,val+ch[0]->rv);
        }
        if (ch[1]!=NULL) {
            s+=ch[1]->s;
            m=max(m,ch[1]->lv+m);
            ma=max(max(ma,m),ch[1]->ma);
            lv=max(lv,sum+ch[1]->lv);
            rv=max(ch[1]->rv,ch[1]->sum+val);
            if(ch[0]!=NULL) rv=max(rv,ch[1]->sum+val+ch[0]->rv);
            sum+=ch[1]->sum;
        }
    }
    void pushdown() {
        if (flip) {
            flip=0;
            if(ch[0]!=NULL) {
                ch[0]->flip^=1;
                swap(ch[0]->ch[0],ch[0]->ch[1]);
                swap(ch[0]->lv,ch[0]->rv);
            }
            if(ch[1]!=NULL) {
                ch[1]->flip^=1;
                swap(ch[1]->ch[0],ch[1]->ch[1]);
                swap(ch[1]->lv,ch[1]->rv);
            }
            swap(lv,rv);
        }
        if (setv!=ini) {
            if (ch[0]!=NULL) {
                ch[0]->val=setv;
                ch[0]->setv=setv;
                ch[0]->sum=setv*ch[0]->s;
                ch[0]->ma=ch[0]->lv=ch[0]->rv=max(setv,ch[0]->sum);
            }
            if (ch[1]!=NULL) {
                ch[1]->val=setv;
                ch[1]->setv=setv;
                ch[1]->sum=setv*ch[1]->s;
                ch[1]->ma=ch[1]->lv=ch[1]->rv=max(setv,ch[1]->sum);
            }
            setv=ini;
        }
    }
};
Node* root=NULL;
void rotate(Node* &o,int d) {
    Node* k = o->ch[d^1];
    Node* par = o->par;
    o->ch[d^1] = k->ch[d];
    if(k->ch[d]) k->ch[d]->par=o;
    k->ch[d] = o;
    o->par=k;
    k->par=par;
    o->maintain();
    k->maintain();
    o=k;
}
void splay(Node* &o,int k) {
    //correct
    o->pushdown();
    o->maintain();
    int d= o->cmp(k);
    if (d==1) k -= o->rank;
    if (d!=-1) {
        Node* p = o->ch[d];
        p->pushdown();
        p->maintain();
        int d2 = p->cmp(k);
        int k2 = (d2==0 ? k : k-p->rank);
        if (d2!=-1) {
            splay(p->ch[d2],k2);
            if (d==d2) rotate(o,d^1);
            else rotate(o->ch[d], d);
        }
        rotate(o,d^1);
    }
}
//Node* id[maxn];
Node* build(int l,int r,Node *fa) {
    Node* p;
    int mid=(l+r)>>1;
    p=new Node();
    p->val=a[mid];
//    id[a[mid]]=p;
    p->s=r-l+1;
    p->rank=mid-l+1;
    p->flip=0;
    p->setv=ini;
    p->par=fa;
    p->ch[0]=p->ch[1]=NULL;
    if (mid-1>=l) p->ch[0]=build(l,mid-1,p);
    if (mid+1<=r) p->ch[1]=build(mid+1,r,p);
    p->maintain();
    return p;
}
void remove(Node* &o) {
    if(o==NULL) return;
    remove(o->ch[0]);
    remove(o->ch[1]);
    delete o;
    o=NULL;
}
// 分裂
void split(Node* o,int k,Node* &left,Node* &right) {
    splay(o,k);
    left=o;
    right=o->ch[1];
    if(right) right->par=NULL;
    o->ch[1]=NULL;
    left->maintain();
//    printf("~~%d\n",left->ch[0]->rv);
}
// 合并
Node* merge(Node* left,Node* right) {
    splay(left, left->s);
    left->ch[1]=right;
    if(right) right->par=left;
    left->maintain();
    return left;
}
void update(int l,int r,int setv) {
    Node *left,*mid,*right,*o;
    split(root,l,left,o);
    split(o,r-l+1,mid,right);
    mid->setv=setv;
    mid->val=setv;
    mid->pushdown();
    mid->maintain();
    root=merge(merge(left,mid),right);
}
void reverse(int l,int r) {
    Node *left,*mid,*right,*o;
    split(root,l,left,o);
    split(o,r-l+1,mid,right);
    mid->flip^=1;
    swap(mid->ch[1],mid->ch[0]);
    mid->pushdown();
    mid->maintain();
    root=merge(merge(left,mid),right);
}
int query(int l,int r) {
    Node *left,*mid,*right,*o;
    split(root,l,left,o);
    split(o,r-l+1,mid,right);
    int ret=mid->sum;
    root=merge(merge(left,mid),right);
    return ret;
}
void addPoint(int pos,int n) {
    Node *mid=build(1,n,NULL);
    Node *left,*right;
    split(root,pos,left,right);
    root=merge(merge(left,mid),right);
}
void delPoint(int pos,int n) {
    Node *left,*mid,*right,*o;
    split(root,pos,left,o);
    split(o,n,mid,right);
    remove(mid);
    root=merge(left,right);
}
int main(int argc, char const *argv[]) {
//    freopen("data.txt","r",stdin);
//    freopen("ans.txt","w",stdout);
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF) {
        remove(root);
        a[0]=-10000;
        for(int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
        }
        root=build(0,n,NULL);
        char op[15];
        while(q--) {
            scanf("%s",op);
            if(op[0]=='M'&&op[2]=='K') {
                int l,r,v;
                scanf("%d%d%d",&l,&r,&v);
                if(r!=0) update(l,l+r-1,v);
            } else if(op[0]=='R') {
                int l,r;
                scanf("%d%d",&l,&r);
                if(r!=0) reverse(l,l+r-1);
            } else if(op[0]=='G') {
                int l,r;
                scanf("%d%d",&l,&r);
                if(r==0) printf("0\n");
                else printf("%d\n",query(l,l+r-1));
            } else if(op[0]=='I') {
                int pos,k;
                scanf("%d%d",&pos,&k);
                for(int i=1; i<=k; i++)
                    scanf("%d",&a[i]);
                addPoint(pos+1,k);
            } else if(op[0]=='D') {
                int pos,k;
                scanf("%d%d",&pos,&k);
                delPoint(pos,k);
            } else {
                printf("%d\n",root->ma==-10000?0:root->ma);
            }
//            print(root);
        }
    }
    return 0;
}
/*
20 50
8 9 4 8 9 -3 8 1 -6 4 8 5 3 0 0 9 -9 9 -5 9
GET-SUM 1 13
MAX-SUM
*/

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
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
 /* 
  该代码默认不去重
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
using namespace std;
struct Node {
    Node *ch[2];
    int r,v,s;//s表示节点数
    Node(int v):v(v) {
        ch[0]=ch[1]=NULL;
        r=rand();//在cstdlib头声明
        s=1;
    }
    bool operator < (const Node &rhs) const {
        return r < rhs.r;
    }
    int cmp(int x) {
        if(x==v)return -1;
        return x<v?0:1;
    }
    void maintain() {
        s=1;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
};
void rotate(Node* &o,int d) {
    Node *k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o->maintain();
    k->maintain();
    o=k;
}
void insert(Node* &o,int x) { //o子树中事先不存在x
    if(o==NULL) o=new Node(x);
    else {
        //如这里改成int d=o->cmp(x);
        //就不可以插入相同的值，因为d可能为-1
        //if(x==o->v) return;  //如果需要去重
        int d=x<(o->v)?0:1;
        insert(o->ch[d],x);
        if(o->ch[d]->r > o->r)
            rotate(o,d^1);
    }
    o->maintain();
}
void erase(Node* &o,int x) {
    if(o==NULL) return ;//空时返回
    int d=o->cmp(x);
    if(d==-1) {
        Node *u=o;
        if(o->ch[0] && o->ch[1]) {
            int d2=(o->ch[0]->r > o->ch[1]->r)?1:0;
            rotate(o,d2);
            erase(o->ch[d2],x);
        } else {
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
            delete u;//这个要放里面
        }
    } else erase(o->ch[d],x);
    if(o) o->maintain();//之前o存在,但是删除节点后o可能就是空NULL了,所以需要先判断o是否为空
}
//返回关键字从小到大排序时的第k个值
int kth(Node* o,int k) {
    if(o==NULL || k<=0 || k>o->s) return 0;//保证输入合法
    int s=(o->ch[0]==NULL)?0:o->ch[0]->s;
    if(k==s+1) return o->v;
    else if(k<=s) return kth(o->ch[0],k);
    else return kth(o->ch[1],k-s-1);
}
//返回值x在树中的排名,就算x不在o树中也能返回排名
//返回值范围在[1,o->s+1]范围内
int rank(Node* o,int x) {
    if(o==NULL) return 1;//未找到x;
    int num= o->ch[0]==NULL ? 0:o->ch[0]->s;
    if(x <= o->v) return rank(o->ch[0],x);
    else return rank(o->ch[1],x)+num+1;
}
int find(Node *o,int x) {
    while(o!=NULL) {
        int d=o->cmp(x);
        if(d==-1)return 1; //存在
        o=o->ch[d];
    }
    return 0;              //不存在
}
int Get_Max(Node *o) {
    while(o->ch[1]!=NULL) o=o->ch[1];
    return o->v;
}
int Get_Min(Node *o) {
    while(o->ch[0]!=NULL) o=o->ch[0];
    return o->v;
}
//不存在则返回y
int get_pre(Node *o,int y,int k) {
    if(o==NULL) return y;
    if(k>o->v)//加个等号就是小于等于
        return get_pre(o->ch[1],o->v,k);
    else return get_pre(o->ch[0],y,k);
}
//不存在则返回y
int get_next(Node *o,int y,int k) {
    if(o==NULL) return y;
    if(k<o->v)//加个等号就是小于等于
        return get_next(o->ch[0],o->v,k);
    else return get_next(o->ch[1],y,k);
}
void init(Node *o) {
    if(o==NULL) return;
    init(o->ch[0]);
    init(o->ch[1]);
    delete o;
    o=NULL;
}
void inorder(Node *o) {
    if(o==NULL) return;
    else {
        inorder(o->ch[0]);
        printf(" %d",o->v);
        inorder(o->ch[1]);
    }
}
Node *root;
int main() {
    int n=0;
    while(scanf("%d",&n)==1 && n) {
        init(root);
        for(int i=0; i<n; i++) {
            int x;
            scanf("%d",&x);
            if(root==NULL) root=new Node(x);
            else insert(root,x);
        }
        int v;
        while(scanf("%d",&v)==1) {
            printf("rank : %d\n",rank(root,v));
            printf("Kth : %d\n",kth(root,v));
            printf("pre : %d\n",get_pre(root,-111,v));
            printf("next : %d\n",get_next(root,-111,v));
            printf("order :");inorder(root);printf("\n");
            printf("max : %d\n",Get_Max(root));
            printf("min : %d\n",Get_Min(root));
        }
    }
    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
 #include<bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node {
    int l,r;
    int mid() {
        return (l+r)>>1;
    }
} tree[N<<2];
int sorted[N];
int val[20][N],toLeft[20][N];
void build(int l,int r,int rt,int deep) {
    tree[rt].l = l;
    tree[rt].r  = r;
    if(l == r) return;
    int m = tree[rt].mid();
    int midval = sorted[m];
    int leftsame = m - l + 1;//表示在左子树上有多少和midval相等的数
    for(int i = l ; i <= r ; i ++) {
        if(val[deep][i] < midval)
            --leftsame;
    }
    int lpos = l,rpos = m + 1;
    for(int i = l ; i <= r ;  i++) {
        if(i == l) toLeft[deep][i] = 0;//toLeft[][i]表示[tree[rt].l,i-1]有多少数在左部
        else toLeft[deep][i] = toLeft[deep][i-1];//这里相当于对toLeft[][]初始化
        if(val[deep][i] < midval) {
            ++toLeft[deep][i];
            val[deep+1][lpos++] = val[deep][i];
        } else if(val[deep][i] > midval) {
            val[deep+1][rpos++] = val[deep][i];
        } else { //判断和midval相等的数是放在左部还是右部
            if(leftsame >= 0) {
                --leftsame;
                ++toLeft[deep][i];
                val[deep+1][lpos++] = val[deep][i];
            } else {
                val[deep+1][rpos++] = val[deep][i];
            }
        }
    }
    build(l,m,rt<<1,deep+1);
    build(m+1,r,rt<<1|1,deep+1);
}
int query(int l,int r,int k,int rt,int deep) {
    if(l == r) return val[deep][l];
    //下面就是要确认新的查找区间
    int s;//表示[l,r]里在左边的数的个数
    int ss;//表示[tree[rt].l,l-1]里在左边的数的个数
    if(l == tree[rt].l) {
        s = toLeft[deep][r];
        ss = 0;
    } else {
        ss = toLeft[deep][l-1];
        s = toLeft[deep][r] - ss;
    }
    //注意这里的在左边的数都是和sorted[m]相比的，由此可以得到如果s>=k就去左子树找，相反则去右子树
    if(s >= k) {
        /*进入左子树，该条线段的左边有ss个数及从是从上面[tree[rt].l,l-1]该进入左子树的数继承而来
        *接着还应该有toLeft[deep][r] - toLeft[deep][l-1]个数即s个数
        *所以可以确定新的查找区间应该是[tree[rt].l+ss,newl+s - 1]
        */
        int newl = tree[rt].l + ss;
        int newr = newl + s - 1;//这里减1是为了处理边界问题
        return query(newl,newr,k,rt<<1,deep+1);
    } else {
        /*
        *进入右子树，该条线段的左边应该是上条线段[tree[rt].l,l-1]应该进入右子树的数，即bb = l - tree[rt].l - ss个数
        *接着还应该有上条线段[l,r]应该进入右子树的数，即b = r - l + 1 - s个数
        *所以可以确定新的查询区间应该是[mid + 1 + bb,mid + 1 + bb + b - 1]，这里的-1同一是为了处理边界问题
        */
        int m = tree[rt].mid();
        int b = r - l + 1 - s;//表示[l,r]在右边的数的个数
        int bb = (l - 1) - tree[rt].l + 1 - ss;//表示[tree[rt].l,l-1]在右边的数的个数
        int newl = m + 1 + bb;
        int newr = m + b + bb;//m + r - l + 1 - toLeft[deep][r] + ss - l - tree[rt].l - ss = m+r-
        return query(newl,newr,k-s,rt<<1|1,deep+1);
    }
}
static inline int Rint() { //这段是整型数的输入外挂，可以忽略不用看
    struct X {
        int dig[256];
        X() {
            for(int i = '0'; i <= '9'; ++i) dig[i] = 1;
            dig['-'] = 1;
        }
    };
    static 	X fuck;
    int s = 1, v = 0, c;
    for (; !fuck.dig[c = getchar()];);
    if (c == '-') s = 0;
    else if (fuck.dig[c]) v = c ^ 48;
    for (; fuck.dig[c = getchar()]; v = v * 10 + (c ^ 48));
    return s ? v : -v;
}
int main() {
    int n,m;
    while(~scanf("%d %d",&n,&m)) {
        for(int i = 1 ; i <= n ;  i++) {
            scanf("%d",&val[0][i]);
            sorted[i] = val[0][i];
        }
        sort(sorted+1,sorted+n+1);
        build(1,n,1,0);
        while(m--) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            printf("%d\n",query(a,b,c,1,0));
        }
    }
    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
 #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <algorithm>
#define MAX 100002
using namespace std;
int n,ub=0,lb=0x7fffffff,kuai;
//ub上界，lb下界，kuai块的大小 
int num[MAX],divd[MAX];
//num原序列，divd分块数组 
int b_s(int l,int r,int a){//二分查找 
	while(l!=r){
		int m=(l+r)>>1;
		if(divd[m]>=a)r=m;
		else l=m+1;
	}
	if(divd[l]>=a)--l;
	return l;
}
void change(int pos,int a)
{
	int l=((pos-1)/kuai)*kuai+1;
	int r=min(n,l+kuai-1);
	int ks=b_s(l,r,num[pos])+1;
	//二分查找位置 
	divd[ks]=a;
	while(divd[ks]<divd[ks-1]&&ks-1>=l){swap(divd[ks],divd[ks-1]);--ks;}
	while(divd[ks]>divd[ks+1]&&ks+1<=r){swap(divd[ks],divd[ks+1]);++ks;}
	//移动到拍好序的位置 
	num[pos]=a;
}
int query(int l,int r,int k){
	int lk=((l-1)/kuai)+1,rk=((r-1)/kuai)-1;
	//确定查询的块 
	int d=lb,u=ub;
	while(d!=u){//二分答案 
		int m=(d+u)>>1;
		int kth=0;
		if(lk<=rk){ //在两边直接查找，块内二分查找 
			for(int i=l;i<=lk*kuai;i++)if(num[i]<m)++kth;
			for(int i=lk;i<=rk;i++)kth+=b_s(i*kuai+1,i*kuai+kuai,m)-i*kuai;
			for(int i=rk*kuai+kuai+1;i<=r;i++)if(num[i]<m)++kth;
		}else for(int i=l;i<=r;i++)if(num[i]<m)++kth;//在同一块内 
		if(kth>=k)u=m;
		else d=m+1;
	}
	return d-1;
}
int main()
{
	//freopen("kth.in","r",stdin);
	int m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&num[i]);
		ub=max(ub,num[i]+1);
		lb=min(lb,num[i]-1);
	}
	//输入，确定上下界 
	memcpy(divd,num,sizeof num);
	kuai=sqrt(n+0.5);
	for(int i=0;i<=kuai;i++)sort(divd+i*kuai+1,divd+min(n,(i+1)*kuai)+1);
	//分块并排序 
	while(m--){
		int r,l,k;
		char q;
		do{scanf("%c",&q);}while(q!='C'&&q!='Q');
		if(q=='C'){//修改 
			scanf("%d%d",&l,&k);
			change(l,k);
			if(k+1>ub)ub=k+1;
			if(k-1<lb)lb=k-1;
			//更新上下界 
		}
		else{//查询 
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",query(l,r,k));
		}
	}
	
	//printf("\nRuntime: %d ms",clock());
	return 0;
}

二维树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int c[MAXN][MAXM];
int n,m;
int lowbit(int x) {
    return x&(-x);
}
int sum(int x,int y) {
    int ret = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        for(int j = y; j > 0; j -= lowbit(j))
            ret += c[i][j];
    return ret;
}
void add(int x,int y,int val) {
    for(int i = x; i <= n; i += lowbit(i))
        for(int j = y; j <= m; j += lowbit(j))
            c[i][j] += val;
}

二维RMQ

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
void init() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &val[i][j]);
            dp[i][j][0][0] = val[i][j];
        }
    for (int i = 0; (1 << i) <= n; i++) {
        for (int j = 0; (1 << j) <= m; j++) {
            if (i == 0 && j == 0) continue;
            for (int row = 1; row + (1 << i) - 1 <= n; row++)
                for (int col = 1; col + (1 << j) - 1 <= m; col++) {
                    //当x或y等于0的时候，就相当于一维的RMQ了
                    if (i == 0) dp[row][col][i][j] = max(dp[row][col][i][j - 1], dp[row][col + (1 << (j - 1))][i][j - 1]);
                    else if (j == 0) dp[row][col][i][j] = max(dp[row][col][i - 1][j], dp[row + (1 << (i - 1))][col][i - 1][j]);
                    else dp[row][col][i][j] = max(dp[row][col][i][j - 1], dp[row][col + (1 << (j - 1))][i][j - 1]);
                }
        }
    }
}
int Query(int x1, int y1, int x2, int y2) {
    int kx = 0, ky = 0;
    while (x1 + (1 << (1 + kx)) - 1 <= x2) kx++;
    while (y1 + (1 << (1 + ky)) - 1 <= y2) ky++;
    int m1 = dp[x1][y1][kx][ky];
    int m2 = dp[x2 - (1 << kx) + 1][y1][kx][ky];
    int m3 = dp[x1][y2 - (1 << ky) + 1][kx][ky];
    int m4 = dp[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky];
    return max(max(m1, m2), max(m3, m4));
}

后缀数组

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
 /*
给两个串S和P，问P在S中不重复匹配多少次
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
char s[maxn];
int sa[maxn],Rank[maxn],height[maxn];
int t1[maxn],t2[maxn],c[maxn],n;
int dmin[maxn][20];
bool cmp(int *y,int a,int b,int k) {
    int a1=y[a];
    int b1=y[b];
    int a2=a+k>=n ? -1:y[a+k];
    int b2=b+k>=n ? -1:y[b+k];
    return a1==b1 && a2==b2;
}
void build_sa(int m) {
    int *x = t1, *y = t2;
    //基数排序
    for(int i = 0; i < m; i++) c[i] = 0;
    for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
    for(int i = 1; i < m; i++) c[i] += c[i-1];
    for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
    for(int k = 1; k <= n; k <<= 1) {
        int p = 0;
        //直接利用sa数组排序第二关键字
        for(int i = n-k; i < n; i++) y[p++] = i;
        for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
        //基数排序第一关键字
        for(int i = 0; i < m; i++) c[i] = 0;
        for(int i = 0; i < n; i++) c[x[y[i]]]++;
        for(int i = 1; i < m; i++) c[i] += c[i-1];
        for(int i = n-1; i>= 0; i--) sa[--c[x[y[i]]]] = y[i];
        //根据sa和y数组计算新的x数组
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for(int i = 1; i < n; i++)
            x[sa[i]]=cmp(y,sa[i],sa[i-1],k) ? p-1:p++;
        if(p >= n) break;
        m = p;
    }
}
void build_height() { //n不能等于1,否则出BUG
    int i,j,k=0;
    for(i=0; i<n; i++) Rank[sa[i]]=i;
    for(i=0; i<n; i++) {
        if(k) k--;
        if(!Rank[i]) continue;
        j=sa[Rank[i]-1];
        while(s[i+k]==s[j+k])k++;
        height[Rank[i]]=k;
    }
}
void initMin() {
    for(int i = 0; i < n; i++) dmin[i][0] = height[i];
    for(int j = 1; (1<<j) <= n; j++)
        for(int i = 0; i + (1<<j) - 1 < n; i++)
            dmin[i][j] = min(dmin[i][j-1], dmin[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R) { //取得范围最小值
    int k=0;
    while((1<<(k+1))<=R-L+1)k++;
    return min(dmin[L][k], dmin[R-(1<<k)+1][k]);
}
int LCP(int i,int j) { //求后缀i和j的LCP最长公共前缀
    int L=Rank[i],R=Rank[j];
    if(L>R) swap(L,R);
    return RMQ(L+1,R);
}
int cmp_suffix(char *P,int p,int c,int &k) {
    int i;
    for(i = 0; P[c+i] == s[sa[p]+c+i]; i++) {
        if(P[c+i] == '\0') return 0;
        k++;
    }
    if(P[c+i] == '\0') return 0;
    return P[c+i] - s[sa[p]+c+i];
}
char P[maxn];
vector<int> vec;
int Find() {
    vec.clear();
    int m=strlen(P);
    int L=0,R=n-1,k,pos=-1;
    if(cmp_suffix(P,L,0,k)<0) return -1;
    if(cmp_suffix(P,R,0,k)>0) return -1;
    k=0;
    while(L<R) {
        int M=(L+R)/2;
        if(pos!=-1&&LCP(sa[pos],sa[M])<k) {
            int r=LCP(sa[pos],sa[M]),t;
            int ans=cmp_suffix(P,M,r,t);
            if(ans>0) L=M+1;
            else R=M;
        } else {
            int ans=cmp_suffix(P,M,k,k);
            if(ans>0) L=M+1;
            else R=M;
            pos=M;
        }
    }
    if(k<m) return -1;
    vec.push_back(sa[L]);
    for(int i=L+1; i<n; i++) {
        if(height[i]>=m) {
            vec.push_back(sa[i]);
        } else break;
    }
}
void init() {
    n=strlen(s);
    build_sa(200);
    build_height();
    initMin();
}
int main() {
    while(scanf("%s",s)!=EOF) {
        if(strcmp(s,"#")==0) break;
        init();
        scanf("%s",P);
        int m=strlen(P);
        Find();
        if(vec.size()==0) printf("0\n");
        else {
            sort(vec.begin(),vec.end());
            int ans=1,pos=vec[0];
            for(int i=1; i<vec.size(); i++) {
                if(vec[i]-pos>=m) {
                    ans++;
                    pos=vec[i];
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}
//DC3版
 ```C++
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define maxn 100010
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[maxn*3],wb[maxn*3],wv[maxn*3],ws[maxn*3];
int r[maxn*3],sa[maxn*3];
int c0(int *r,int a,int b) {
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b) {
    if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
    else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
}
void sort(int *r,int *a,int *b,int n,int m) {
    int i;
    for(i=0; i<n; i++) wv[i]=r[a[i]];
    for(i=0; i<m; i++) ws[i]=0;
    for(i=0; i<n; i++) ws[wv[i]]++;
    for(i=1; i<m; i++) ws[i]+=ws[i-1];
    for(i=n-1; i>=0; i--) b[--ws[wv[i]]]=a[i];
    return;
}
void dc3(int *r,int *sa,int n,int m) {
    int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    r[n]=r[n+1]=0;
    for(i=0; i<n; i++) if(i%3!=0) wa[tbc++]=i;
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++)
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
    else for(i=0; i<tbc; i++) san[rn[i]]=i;
    for(i=0; i<tbc; i++) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0; i<tbc; i++) wv[wb[i]=G(san[i])]=i;
    for(i=0,j=0,p=0; i<ta && j<tbc; p++)
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(; i<ta; p++) sa[p]=wa[i++];
    for(; j<tbc; p++) sa[p]=wb[j++];
    return;
}
int Rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1; i<=n; i++) Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
    return;
}
int RMQ[maxn];
int mm[maxn];
int best[20][maxn];
void initRMQ(int n) {
    int i,j,a,b;
    for(mm[0]=-1,i=1; i<=n; i++)
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
    for(i=1; i<=n; i++) best[0][i]=i;
    for(i=1; i<=mm[n]; i++)
        for(j=1; j<=n+1-(1<<i); j++) {
            a=best[i-1][j];
            b=best[i-1][j+(1<<(i-1))];
            if(RMQ[a]<RMQ[b]) best[i][j]=a;
            else best[i][j]=b;
        }
    return;
}
int askRMQ(int a,int b) {
    int t;
    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) {
    if(a==b) return maxn;
    a=Rank[a];b=Rank[b];
    if(a>b) swap(a,b);
    return(height[askRMQ(a+1,b)]);
}
char c[maxn];
int main() {
    int ca;
    scanf("%d",&ca);
    while(ca--) {
        scanf("%s",c);
        int n=strlen(c);
        for(int i=0; i<n; i++) {
            if(c[i]<'a') r[i]=c[i]-'A'+1;
            else r[i]=c[i]-'a'+1+26;
        }
        r[n]=0;
        dc3(r,sa,n+1,55);
        calheight(r, sa, n);
        initRMQ(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
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
#define maxn 222
struct Point{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y) {}
    void in(){
        scanf("%lf%lf",&x,&y);
    }
};
Point A[maxn],B[maxn];
double va[maxn];
struct SegTree{
    double sumv[maxn*4];
    int addv[maxn*4];
    void maintain(int o,int L,int R){
        sumv[o]=0;
        if(addv[o]) sumv[o]=va[R]-va[L-1];
        else if(R>L) sumv[o]=sumv[o*2]+sumv[o*2+1];
    }
    void update(int o,int L,int R,int qL,int qR,double v){
        if(L==R){
            addv[o]+=v;
        }else{
            int M=L+(R-L)/2;
            if(qL<=M) update(o*2,L,M,qL,qR,v);
            if(qR>M) update(o*2+1,M+1,R,qL,qR,v);
        }
        maintain(o,L,R);
        //printf("~~%d %d %d %f %d\n",o,L,R,sumv[o],addv[o]);
    }
};
SegTree T;
struct Line{
    int l,r;
    double h;
    int d;
    bool operator <(const Line &a) const{
        return h<a.h;
    }
}line[maxn];
int main(){
    int n,kase=0;
    while(~scanf("%d",&n)&&n){
        int len=1,k=0;
        memset(&T,0,sizeof(T));
        for(int i=0;i<n;i++){
            A[i].in();B[i].in();
            va[len++]=A[i].x;
            va[len++]=B[i].x;
        }
        sort(va+1,va+len);
        len=unique(va+1,va+len)-va;
        for(int i=0;i<n;i++){
            int x1=lower_bound(va+1,va+len,A[i].x)-va;
            int x2=lower_bound(va+1,va+len,B[i].x)-va;
            line[k++]=(Line){x1,x2,A[i].y,1};
            line[k++]=(Line){x1,x2,B[i].y,-1};
        }
        sort(line,line+k);
        double ans=0;
        for(int i=0;i<k-1;i++){
            T.update(1,1,len,line[i].l+1,line[i].r,line[i].d);
            //printf("%d %d %f %d %f\n",line[i].l,line[i].r,line[i].h,line[i].d,T.sumv[1]);
            ans+=T.sumv[1]*(line[i+1].h-line[i].h);
            //printf(" %f\n",ans);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++kase,ans);
    }
    return 0;
}
/*
4
0 0 5 5
4 4 6 6
5 5 7 7
0 0 2 2
*/

矩阵周长——线段树

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;
#define N 10001
#define maxn 20010
struct Poll{
    ll x,y;
    Poll(ll x=0,ll y=0):x(x),y(y) {}
    void in(){
        scanf("%lld%lld",&x,&y);
        x+=N;y+=N;
    }
};
Poll A[maxn],B[maxn];
struct SegTree{
    ll sumv[maxn*4],addv[maxn*4];
    void mallain(ll o,ll L,ll R){
        sumv[o]=0;
        if(addv[o]) sumv[o]=R-L+1;
        else if(R>L) sumv[o]=sumv[o*2]+sumv[o*2+1];
    }
    void update(ll o,ll L,ll R,ll qL,ll qR,ll v){
        if(qL<=L&&R<=qR){
            addv[o]+=v;
        }else{
            ll M=L+(R-L)/2;
            if(qL<=M) update(o*2,L,M,qL,qR,v);
            if(qR>M) update(o*2+1,M+1,R,qL,qR,v);
        }
        mallain(o,L,R);
        //prllf("---%d %d %d %d\n",L,R,sumv[o],addv[o]);
    }
    ll query(ll o,ll L,ll R,ll qL,ll qR){
        if(addv[o]) return min(R,qR)-max(L,qL)+1;
        if(qL<=L&&R<=qR) return sumv[o];
        ll M=L+(R-L)/2;
        ll ans=0;
        if(qL<=M) ans+=query(o*2,L,M,qL,qR);
        if(qR>M) ans+=query(o*2+1,M+1,R,qL,qR);
        return ans;
    }
};
SegTree T;
struct Line{
    ll l,r;
    ll h;
    ll d;
    bool operator <(const Line &a) const{
        return h<a.h||h==a.h&&d>a.d;
    }
}H[maxn],W[maxn];
int main(){
    ll n;
//    freopen("data.txt","r",stdin);
    while(~scanf("%lld",&n)){
        ll a=0,b=0;
        for(ll i=0;i<n;i++){
            A[i].in();B[i].in();
            H[a++]=(Line){A[i].x,B[i].x,A[i].y,1};
            H[a++]=(Line){A[i].x,B[i].x,B[i].y,-1};
            W[b++]=(Line){A[i].y,B[i].y,A[i].x,1};
            W[b++]=(Line){A[i].y,B[i].y,B[i].x,-1};
        }
        sort(H,H+a);sort(W,W+b);
        ll ans=0;
        memset(&T,0,sizeof(T));
        for(ll i=0;i<a;i++){
            ll l=H[i].l,r=H[i].r;
            ans+=r-l-T.query(1,1,2*N,l+1,r);
            //prllf("%d %d %d %d\n",l,r,H[i].d,T.query(1,1,2*N,l+1,r));
            T.update(1,1,2*N,l+1,r,H[i].d);
        }
        memset(&T,0,sizeof(T));
        for(ll i=0;i<b;i++){
            ll l=W[i].l,r=W[i].r;
            ans+=r-l-T.query(1,1,2*N,l+1,r);
            //printf("%lld %lld %lld %lld\n",l,r,T.query(1,1,2*N,l+1,r),ans);
            T.update(1,1,2*N,l+1,r,W[i].d);
        }
        printf("%lld\n",ans*2);
    }
    return 0;
}
/*
2
0 0 5 3
5 0 6 3
*/

高维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//num[j]表示状态j中为0的为位置不确定的前缀和
//以下数均为二进制
//如num[1010]=count[1010]+count[1110]+count[1011]+count[1111];
#include <cstdio>
using namespace std;
int num[1<<21];
int main()
{
    int k;
    scanf("%d",&k);
    int fk=(1<<k)-1;
    num[(1<<k)-1]=1;
    for(int i=0; i<k; i++) {    //要先枚举位置，否则出错
        for(int j=fk; j>=0; j--) {
            if(!((1<<i)&j)) num[j]+=num[j|(1<<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
98
99
100
101
102
103
104
105
106
107
108
 一、康托展开：全排列到一个自然数的双射
 
X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!
 
ai为整数，并且0<=ai<i(1<=i<=n)
 
 适用范围：没有重复元素的全排列
 
 
二、全排列的编码：
 
{1,2,3,4,...,n}的排列总共有n!种，将它们从小到大排序，怎样知道其中一种排列是有序序列中的第几个？
 
如 {1,2,3} 按从小到大排列一共6个：123 132 213 231 312 321。想知道321是{1,2,3}中第几个大的数。
 
这样考虑：第一位是3，小于3的数有1、2 。所以有2*2!个。再看小于第二位，小于2的数只有一个就是1 ，所以有1*1!=1 所以小于32
 
的{1,2,3}排列数有2*2!+1*1!=5个。所以321是第6个大的数。2*2!+1*1!是康托展开。（注意判断排列是第几个时要在康托展开的结果后+1）
 
再举个例子：1324是{1,2,3,4}排列数中第几个大的数：第一位是1小于1的数没有，是0个，0*3!，第二位是3小于3的数有1和2，但1已经在第一位了，所以只有一个数2，1*2! 。第三位是2小于2的数是1，但1在第一位，所以有0个数，0*1!，所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。
 
又例如，排列3 5 7 4 1 2 9 6 8展开为98884，因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.
 
解释：
 
排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!
 
排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为3*7!
 
以此类推，直至0*0!
 
//编码从1开始
#include<cstdio>
const int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};///阶乘
int KT(int s[], int n) {
    int i, j, cnt, sum;
    sum = 0;
    for (i = 0; i < n; ++i) {
        cnt = 0;
        for (j = i + 1; j < n; ++j)
            if (s[j] < s[i]) ++cnt;
        sum += cnt * fac[n - i - 1];
    }
    return sum+1;
}
int main() {
    int a[] = {3, 5, 7, 4, 1, 2, 9, 6, 8};
    printf("%d\n", 1 + KT(a, sizeof(a) / sizeof(*a))); ///1+98884
}
 
三、全排列的解码
如何找出第16个（按字典序的）{1,2,3,4,5}的全排列？
 
1. 首先用16-1得到15
 
2. 用15去除4! 得到0余15
 
3. 用15去除3! 得到2余3
 
4. 用3去除2! 得到1余1
 
5. 用1去除1! 得到1余0
 
有0个数比它小的数是1，所以第一位是1
 
有2个数比它小的数是3，但1已经在之前出现过了所以是4
 
有1个数比它小的数是2，但1已经在之前出现过了所以是3
 
有1个数比它小的数是2，但1,3,4都出现过了所以是5
 
最后一个数只能是2
 
所以排列为1 4 3 5 2
 
#include<cstdio>
#include<cstring>
const int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};///阶乘
bool vis[10];
///n为ans大小，k为全排列的编码
void invKT(int ans[], int n, int k) {
    int i, j, t;
    memset(vis, 0, sizeof(vis));
    --k;
    for (i = 0; i < n; ++i) {
        t = k / fac[n - i - 1];
        for (j = 1; j <= n; j++)
            if (!vis[j]) {
                if (t == 0) break;
                --t;
            }
        ans[i] = j, vis[j] = true;
        k %= fac[n - i - 1];///余数
    }
}
int main() {
    int a[10];
    invKT(a, 5, 16);
    for (int i = 0; i < 5; ++i)
        printf("%d ", a[i]);///1 4 3 5 2
}

莫队算法

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
 struct Query{
    int L, R, ID, block;
    Query(){}　　// 构造函数重载
    Query(int l, int r, int ID):L(l), R(r), ID(ID){
        block = l / len;
    }
    bool operator < (const Query rhs) const {
        if(block == rhs.block) return R < rhs.R;　　// 不是if(L == rhs.L) return R < rhs.R; return L < rhs.L
        return block < rhs.block;　　　　　　　　　　 // 否则这就变回算法一了
    }
}queries[maxm];
map<int, int> buf;
inline void insert(int n){
    if(buf.count(n))
        ++buf[n];
    else
        buf[n] = 1;
}
inline void erase(int n){
    if(--buf[n] == 0) buf.erase(n);
}
int A[maxn];　　　　　　　　// 原序列
queue<int> anss[maxm];　　// 存储答案
int main(){
    int n, m;
    cin >> n;
    len = (int)sqrt(n);　　　　// 块长度
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        int l, r;
        cin >> l >> r;
        queries[i] = Query(l, r, i);
    }
    sort(queries + 1, queries + m + 1);
    int L = 1, R = 1;
    buf[A[1]] = 1;
    for(int i = 1; i <= m; i++){
        queue<int>& ans = anss[queries[i].ID];
        Query &qi = queries[i];
        while(R < qi.R) insert(A[++R]);
        while(L > qi.L) insert(A[--L]);
        while(R > qi.R) erase(A[R--]);
        while(L < qi.L) erase(A[L++]);
        for(map<int, int>::iterator it = buf.begin(); it != buf.end(); ++it){
            if(it->second >= 2){
                ans.push(it->first);
            }
        }
    }
    for(int i = 1; i <= m; i++){
        queue<int>& ans = anss[i];
        while(!ans.empty()){
            cout << ans.front() << ' ';
            ans.pop();
        }
        cout << endl;
    }
}

树分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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
 /*
  给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 200010
#define inf 0x3f3f3f3f
struct node {
    int y,v,next;
} e[maxn*2];
int n,k,len,root,sum,ans=inf,Link[maxn],f[maxn],vis[maxn],son[maxn];
ll d[maxn];
struct P{
    ll s;
    int ed,h;
    P(ll s=0,int ed=0,int h=0):s(s),ed(ed),h(h) {};
    bool operator <(const P &rhs)const{
        return s<rhs.s;
    }
}t[maxn];
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))  {
        if(ch=='-')  f=-1;
        ch=getchar();
    }
    while(isdigit(ch))  {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void insert(int x,int y,int v) {
    e[++len].next=Link[x];
    Link[x]=len;
    e[len].y=y;
    e[len].v=v;
}
void getroot(int x,int fa) {
    son[x]=1;
    f[x]=0;
    for(int i=Link[x]; i; i=e[i].next) {
        if(e[i].y==fa||vis[e[i].y])  continue;
        getroot(e[i].y,x);
        son[x]+=son[e[i].y];
        f[x]=max(f[x],son[e[i].y]);
    }
    f[x]=max(f[x],sum-son[x]);
    if(f[x]<f[root])  root=x;
}
int L=0;
void getdeep(int x,int fa,int pre,int ed) {
    t[L++]=P(d[x],ed,pre);
    for(int i=Link[x]; i; i=e[i].next) {
        if(e[i].y==fa||vis[e[i].y])  continue;
        d[e[i].y]=d[x]+e[i].v;
        getdeep(e[i].y,x,pre,ed+1);
    }
}
void cal(int x) {
    d[x]=L=0;
    t[L++]=P(0,0,0);
    for(int i=Link[x]; i; i=e[i].next){
        if(!vis[e[i].y]){
            d[e[i].y]=e[i].v;
            getdeep(e[i].y,x,e[i].y,1);
        }
    }
    sort(t,t+L);
    int l=0,r=L-1;
    while(l<r){
        if(t[r].s+t[l].s>k) r--;
        else{
            for(int i=r;i>l;i--){
                if(t[i].s+t[l].s<k) break;
                if(t[i].h==t[l].h) continue;
                ans=min(ans,t[i].ed+t[l].ed);
            }
            l++;
        }
    }
}
void solve(int x) {
    vis[x]=1;
    cal(x);
    for(int i=Link[x]; i; i=e[i].next) {
        if(vis[e[i].y])  continue;
        root=0;
        sum=son[e[i].y];
        getroot(e[i].y,0);
        solve(root);
    }
}
int main() {
    n=read();k=read();
    for(int i=1; i<n; i++) {
        int x=read(),y=read(),v=read();
        x++;y++;
        insert(x,y,v);
        insert(y,x,v);
    }
    sum=n;
    f[0]=n;
    getroot(1,0);
    solve(root);
    if(ans>=n) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}
/*
4 3
0 1 1
1 2 2
1 3 4
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define INF 0x7fffffff
struct node{int y,v,next;}e[20010];
int n,len,k,root,sum,ans,Link[10010],f[10010],vis[10010],son[10010],d[10010],deep[10010];
inline int read()
{
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
void insert(int x,int y,int v)
{
    e[++len].next=Link[x];
    Link[x]=len;
    e[len].v=v;
    e[len].y=y;
}
void getroot(int x,int fa)
{
    son[x]=1;  f[x]=0;
    for(int i=Link[x];i;i=e[i].next)
    {
        if(e[i].y==fa||vis[e[i].y])  continue;
        getroot(e[i].y,x);
        son[x]+=son[e[i].y];
        f[x]=max(f[x],son[e[i].y]);
    }
    f[x]=max(f[x],sum-son[x]);
    if(f[x]<f[root])  root=x;
}
void getdeep(int x,int fa)
{
    deep[++deep[0]]=d[x];
    for(int i=Link[x];i;i=e[i].next)
    {
        if(e[i].y==fa||vis[e[i].y])  continue;
        d[e[i].y]=d[x]+e[i].v;
        getdeep(e[i].y,x);
    }
}
int cal(int x,int v)
{
    d[x]=v;  deep[0]=0;
    getdeep(x,0);
    sort(deep+1,deep+deep[0]+1);
    int l=1,r=deep[0],sum=0;
    while(l<r)
    {
        if(deep[l]+deep[r]<=k)  {sum+=r-l;  l++;}
        else r--;
    }
    return sum;
}
void solve(int x)
{
    ans+=cal(x,0);//计算答案
    vis[x]=1;
    for(int i=Link[x];i;i=e[i].next)
    {
        if(vis[e[i].y])  continue;
        ans-=cal(e[i].y,e[i].v);//计算不符合题意的答案
        sum=son[e[i].y];
        root=0;
        getroot(e[i].y,0);
        solve(root);
    }
}
int main()
{
    freopen("cin.in","r",stdin);
    freopen("cout.out","w",stdout);
    while(1)
    {
        ans=0,root=0,len=0;
        memset(vis,0,sizeof(vis));
        memset(Link,0,sizeof(Link));
        n=read();  k=read();
        if(n==0&&k==0)  break;
        for(int i=1;i<=n-1;i++)
        {
            int x=read(),y=read(),v=read();
            insert(x,y,v);   insert(y,x,v);
        }
        f[0]=INF;  sum=n;
        getroot(1,0);
        solve(root);
        printf("%d\n",ans);
    }
    return 0;
}

###动态树分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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
 /*
给定一棵树，要求维护以下操作：
1、M u 将u节点反色
2、Q u 查询u到所有黑色节点距离和
初始时所有点都是白色
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 200010
using namespace std;
typedef long long ll;
int n, m;
//-------------------------------------------------//
struct Edge {
    int to, nxt, dis;
} edge[maxn << 1];
int h[maxn], cnt;
void add(int u, int v, int d) {
    cnt ++;
    edge[cnt].to = v;
    edge[cnt].nxt = h[u];
    edge[cnt].dis = d;
    h[u] = cnt;
}
//-------------------------------------------------//
ll dis[maxn];
int dep[maxn], fa[maxn], anc[maxn][20];
void dfs(int u) {
    dep[u] = dep[fa[u]] + 1;
    for(int i = h[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if(v == fa[u])continue;
        dis[v] = dis[u] + edge[i].dis;
        fa[v] = u;
        dfs(v);
    }
}
int ask_LCA(int p, int q) {
    if(dep[p] < dep[q])swap(p, q);
    int log = 1;
    for(; 1 << log <= dep[p]; log ++);
    log --;
    for(int i = log; i >= 0; i --)
        if(anc[p][i] && dep[anc[p][i]] >= dep[q])
            p = anc[p][i];
    if(p == q)return p;
    for(int i = log; i >= 0; i --)
        if(anc[p][i] && anc[p][i] != anc[q][i])
            p = anc[p][i], q = anc[q][i];
    return fa[p];
}
ll dist(int p, int q) {
    return dis[p] + dis[q] - 2 * dis[ask_LCA(p, q)];
}
//-------------------------------------------------//
int g[maxn], size[maxn], G, Sum;
bool vis[maxn], check[maxn];
void Get_G(int u, int fa) {
    size[u] = 1;
    int f = 0;
    for(int i = h[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if(v == fa || vis[v])continue;
        Get_G(v, u);
        size[u] += size[v];
        f = max(f, size[v]);
    }
    f = max(f, Sum - size[u]);
    if((f << 1) <= Sum)G = u;
}
void Divide(int u, int f) {
    g[u] = f;
    vis[u] = true;
    for(int i = h[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if(vis[v])continue;
        Sum = size[v], G = v;
        Get_G(v, u);
        Divide(G, u);
    }
}
//-------------------------------------------------//
ll Node[maxn], Dis[maxn], Disf[maxn], ans;
int Standard;
void White(int u) {
    Node[u] --;
    Dis[u] -= dist(u, Standard);
    if(g[u] == -1)return;
    Disf[u] -= dist(g[u], Standard);
    White(g[u]);
}
void Black(int u) {
    Node[u] ++;
    Dis[u] += dist(u, Standard);
    if(g[u] == -1)return;
    Disf[u] += dist(g[u], Standard);
    Black(g[u]);
}
void ask(int u) {
    ans += (Node[u] * dist(u, Standard) + Dis[u]);
    if(g[u] == -1)return;
    ans -= (Node[u] * dist(g[u], Standard) + Disf[u]);
    ask(g[u]);
}
int main() {
    scanf("%d%d", &n, &m);
    int u, v, d;
    for(int i = 1; i < n; i ++) {
        scanf("%d%d%d", &u, &v, &d);
        add(u, v, d), add(v, u, d);
    }
    dfs(1);
    Sum = n;
    Get_G(1, -1), Divide(G, -1);
    for(int i = 1; i <= n; i ++)
        anc[i][0] = fa[i];
    for(int j = 1; 1 << j <= n; j ++)
        for(int i = 1; i <= n; i ++)
            anc[i][j] = anc[anc[i][j-1]][j-1];
    char cmd[2];
    while(m --) {
        scanf("%s%d", cmd, &u);
        Standard = u;
        if(cmd[0] == 'Q') {
            ans = 0;
            ask(u);
            printf("%lld\n", ans);
        } else {
            if(check[u])White(u);
            else Black(u);
            check[u] ^= 1;
        }
    }
    return 0;
}
版本2：
/*
题目大意：给一颗n个节点的树，边权均为1，初始点权均为0，m次操作： 
Q x：询问x的点权。 
M x d w：将树上与节点x距离不超过d的节点的点权均加上w
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 1000000000
#define N 200003
using namespace std;
struct data{
  int ls,rs,x;
}tr[N*60];
int n,m,root[N],root1[N],point[N],nxt[N],v[N],ans,sum,rt,tot,sz;
int f[N],mi[20],fa[N][20],size[N],deep[N],vis[N],belong[N];
void getroot(int x,int fa)
{
    f[x]=0; size[x]=1;
    for (int i=point[x];i;i=nxt[i]) {
     if (v[i]==fa||vis[v[i]]) continue;
     getroot(v[i],x);
     size[x]+=size[v[i]];
     f[x]=max(f[x],size[v[i]]);
    }
    f[x]=max(f[x],sum-size[x]);
    if (f[x]<f[rt]) rt=x;
}
void dfs(int x,int father)
{
    deep[x]=deep[father]+1;
    for (int i=1;i<=17;i++){
      if (deep[x]-mi[i]<0) break;
      fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for (int i=point[x];i;i=nxt[i]) {
      if (v[i]==father) continue;
      fa[v[i]][0]=x;
      dfs(v[i],x);
    }
}
int lca(int x,int y)
{
    if (deep[x]<deep[y]) swap(x,y);
    int k=deep[x]-deep[y];
    for (int i=0;i<=17;i++) 
     if ((k>>i)&1) x=fa[x][i];
    if (x==y) return x;
    for (int i=17;i>=0;i--)
     if (fa[x][i]!=fa[y][i]) 
      x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int dis(int x,int y)
{
    return deep[x]+deep[y]-2*deep[lca(x,y)];
}
void build(int x)
{
    vis[x]=1;
    for (int i=point[x];i;i=nxt[i]) {
       if (vis[v[i]]) continue;
       rt=0; sum=size[v[i]];
       getroot(v[i],x);
       belong[rt]=x;
       build(rt);
    }
}
void insert(int &i,int l,int r,int x,int d)
{
     if (!i) i=++sz;
     tr[i].x+=d;
     if (l==r) return;
     int mid=(l+r)/2;
     if (x<=mid) insert(tr[i].ls,l,mid,x,d); 
     else insert(tr[i].rs,mid+1,r,x,d);
}
int query(int now,int l,int r,int ll,int rr)
{
    if (ll<=l&&r<=rr) return tr[now].x;
    int mid=(l+r)/2;
    int ans=0;
    if (ll<=mid) ans+=query(tr[now].ls,l,mid,ll,rr);
    if (rr>mid) ans+=query(tr[now].rs,mid+1,r,ll,rr);
    return ans;
}
void change(int u,int x,int d,int w)
{
   int D=dis(u,x);
   if (d-D>=0) insert(root[u],0,n,d-D,w);
   //cout<<u<<" "<<d<<" "<<w<<endl;
   int v=belong[u];
   if (!v) return;
   D=dis(x,v);
   if (d-D>=0) insert(root1[u],0,n,d-D,w);
   change(v,x,d,w);
}
void calc(int u,int x)
{
   if (u==x) ans+=query(root[u],0,n,0,n);
   else {
      int d=dis(u,x); //cout<<u<<" "<<x<<" "<<d<<endl; 
      ans+=query(root[u],0,n,d,n);
      //cout<<u<<" "<<query(root[u],0,n,d,n)<<endl;
   }
   if (!belong[u]) return;
   int d=dis(belong[u],x);
   ans-=query(root1[u],0,n,d,n);
   calc(belong[u],x);
}
void add(int x,int y)
{
    tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
    tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
int main()
{
    freopen("a.in","r",stdin);
    freopen("my.out","w",stdout);
    mi[0]=1;
    for (int i=1;i<=18;i++) mi[i]=mi[i-1]*2;
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++) {
       int x,y; scanf("%d%d",&x,&y);
       add(x,y);
    }
    dfs(1,0);
    rt=0; f[0]=inf; sum=n;
    getroot(1,0); build(rt);
   // cout<<rt<<endl;
   // for (int i=1;i<=n;i++) cout<<belong[i]<<" "; cout<<endl;
    for (int i=1;i<=m;i++) {
      char s[10]; 
      int x,d,w;
      scanf("%s%d",s,&x);
      if (s[0]=='M') {
        scanf("%d%d",&d,&w);
        d=min(d,n);
        change(x,x,d,w);
       }
      else {
         ans=0;
         calc(x,x);
         printf("%d\n",ans);
      }
    }
}

树链剖分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
 /*
 CHANGE a b : change the cost of the a-th edge to b
 QUERY a b : ask for the maximum edge cost on the path from node a to node b 
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
int size[maxn],dep[maxn],val[maxn],id[maxn],hson[maxn],top[maxn],fa[maxn];//定义
int num;
vector<int> g[maxn];
struct tree {
    int x,y,z;
    void init() {
        scanf("%d%d%d",&x,&y,&z);
        g[x].push_back(y);
        g[y].push_back(x);
    }
} e[maxn]; //起点重点权值
struct SegTree{
    int maxv[maxn*4];
    void build(int o,int L,int R){
        if(L==R){
            maxv[o]=val[L];
        }else{
            int M=(L+R)/2;
            build(o*2,L,M);build(o*2+1,M+1,R);
            maxv[o]=max(maxv[o*2],maxv[o*2+1]);
        }
    }
    void update(int o,int L,int R,int p,int v){
        if(L==R) maxv[o]=v;
        else{
            int M=(L+R)/2;
            if(p<=M) update(o*2,L,M,p,v);
            else update(o*2+1,M+1,R,p,v);
            maxv[o]=max(maxv[o*2],maxv[o*2+1]);
        }
    }
    int query(int o,int L,int R,int qL,int qR){
//        printf("%d %d %d %d\n",L,R,qL,qR);
        if(qL<=L&&R<=qR) return maxv[o];
        int ans=0,M=(L+R)/2;
        if(qL<=M) ans=max(ans,query(o*2,L,M,qL,qR));
        if(qR>M) ans=max(ans,query(o*2+1,M+1,R,qL,qR));
        return ans;
    }
}T;
void dfs1(int d,int f,int u) { //d：深度 f:父节点 u：当前节点
    dep[u]=d;
    size[u]=1;
    hson[u]=0;
    fa[u]=f;
    for(vector<int>::iterator it=g[u].begin(); it!=g[u].end(); it++) {
        if(*it==f) continue;
        dfs1(d+1,u,*it);
        size[u]+=size[*it];
        if(size[hson[u]]<size[*it])
            hson[u]=*it;//找重儿子
    }
}
void dfs2(int u,int tp) {
    top[u]=tp;//赋值top
    id[u]=num++;//赋值id
    if(hson[u]) dfs2(hson[u],tp);//优先重儿子
    for(vector<int>::iterator it=g[u].begin(); it!=g[u].end(); it++) {
        if(*it==fa[u]||*it==hson[u]) continue;
        dfs2(*it,*it);
    }
}
int find(int u,int v,int n) {
    int t1=top[u],t2=top[v];
    int ans=0;
    while(t1!=t2) {
        if(dep[t1]<dep[t2]) {
            swap(t1,t2);
            swap(u,v);
        }
        ans=max(T.query(1,2,n,id[t1],id[u]),ans);
        u=fa[t1];
        t1=top[u];
    }
    if(u==v) return ans;
    if (dep[u] > dep[v]) swap(u, v);
    ans = max(T.query(1,2,n,id[hson[u]], id[v]), ans);
    return ans;
}
void init(int n) {
    dfs1(1,0,1);
    dfs2(1,1);
    for(int i=1; i<n; i++) {
        if(dep[e[i].x]<dep[e[i].y])
            swap(e[i].x, e[i].y);
        val[id[e[i].x]] = e[i].z;
    }
    T.build(1,2,n);
}
int main() {
    int ca;
    scanf("%d",&ca);
    while(ca--) {
        int n;
        scanf("%d",&n);
        for(int i=0;i<=n+1;i++) g[i].clear();
        num=1;
        for(int i=1;i<n;i++)
            e[i].init();
        init(n);
        char op[15];
        int a,b;
        while(scanf("%s",op)){
            if(op[0]=='D') break;
            scanf("%d%d",&a,&b);
            if(op[0]=='Q'){
                printf("%d\n",find(a,b,n));
            }else{
                T.update(1,2,n,id[e[a].x],b);
            }
        }
    }
    return 0;
}
/*
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
*/

树状数组区间修改

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
 /*
原理：
首先依旧是引入delta数组 delta[i]表示区间 [i, n] 的共同增量 于是修改区间 [l, r] 时修改 delta[l] 和 delta[r + 1] 即可（就是差分的思路）
查询的时候是查询区间 [l, r] 的和 即sum[r] - sum[l - 1] 所以现在的问题是求sum[i]
sum[i] = a[1]+...+a[i] + delta[1]*i + delta[2]*(i - 1) + delta[3]*(i - 2)+...+delta[i]*1   // a[i]为原始数组
       = sigma( a[x] ) + sigma( delta[x]  *  (i + 1 - x) )
       = sigma( a[x] ) + (i + 1) * sigma( delta[x] ) - sigma( delta[x] * x )
*/
#include <cstdio>
#include <iostream>
#define lowbit(i) (i & (-i))
using namespace std;
int readint()
{
	int sign = 1, n = 0; char c = getchar();
	while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar(); }
	while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }
	return sign*n;
}
const int Nmax = 200100;
int N, Q;
long long delta[Nmax]; // delta的前缀和 
long long deltai[Nmax]; // delta * i的前缀和 
long long sum[Nmax]; // 原始前缀和
long long Query(long long *array, int pos)
{
	long long temp = 0ll;
	while(pos > 0)
	{
		temp += array[pos];
		pos -= lowbit(pos);
	}
	return temp;
}
void Update(long long *array, int pos, int x)
{
	while(pos <= N)
	{
		array[pos] += x;
		pos += lowbit(pos);
	}
}
int main()
{
	N = readint();
	
	for(int i = 1; i <= N; ++i)
	{
		int x = readint();
		sum[i] = sum[i - 1] + x;
	}
	
	Q = readint();
	
	while(Q--)
	{
		int sign = readint();
		if(sign == 1) // 修改：把[l, r]区间均加上x 
		{
			int l = readint(), r = readint(), x = readint();
			Update(delta, l, x);
			Update(delta, r+1, -x);
			Update(deltai, l, x * l);
			Update(deltai, r+1, -x * (r+1));
		} 
		else // 查询：[l, r]区间和 
		{
			int l = readint(), r = readint(); 
			long long suml = sum[l - 1] + l * Query(delta, l - 1) - Query(deltai, l - 1);
			long long sumr = sum[r] + (r + 1) * Query(delta, r) - Query(deltai, r);
			printf("%lld\n", sumr - suml);
		}
	}
	
	return 0;
}

数位dp

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
 //    pos    = 当前处理的位置(一般从高位到低位)
//    pre    = 上一个位的数字(更高的那一位)
//    status = 要达到的状态,如果为1则可以认为找到了答案,到时候用来返回,
//         　　 给计数器+1。
//    limit  = 是否受限,也即当前处理这位能否随便取值。如567,当前处理6这位,
//         　　 如果前面取的是4,则当前这位可以取0-9。如果前面取的5,那么当前
//         　　 这位就不能随便取，不然会超出这个数的范围,所以如果前面取5的
//         　　 话此时的limit=1,也就是说当前只可以取0-6。
//
//    用DP数组保存这三个状态是因为往后转移的时候会遇到很多重复的情况。
int    dfs(int pos,int pre,int status,int limit)
{
    //已结搜到尽头,返回"是否找到了答案"这个状态。
    if(pos < 1)
        return    status;
    //DP里保存的是完整的,也即不受限的答案,所以如果满足的话,可以直接返回。
    if(!limit && DP[pos][pre][status] != -1)
        return    DP[pos][pre][status];
    int    end = limit ? DIG[pos] : 9;
    int    ret = 0;
    
    //往下搜的状态表示的很巧妙,status用||是因为如果前面找到了答案那么后面
    //还有没有答案都无所谓了。而limti用&&是因为只有前面受限、当前受限才能
    //推出下一步也受限，比如567,如果是46X的情况,虽然6已经到尽头,但是后面的
    //个位仍然可以随便取,因为百位没受限,所以如果个位要受限,那么前面必须是56。
    //
    //这里用"不要49"一题来做例子。
    for(int i = 0;i <= end;i ++)
        ret += dfs(pos - 1,i,status || (pre == 4 && i == 9),limit && (i == end));
    //DP里保存完整的、取到尽头的数据
    if(!limit)
        DP[pos][pre][status] = ret;
    return    ret;
}

拓展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
 //C/C++ 模板
#include<iostream>
using namespace std;
const int N = 101010;
int next[N],extand[N];
void getnext(char *T) { // next[i]: 以第i位置开始的子串 与 T的公共前缀
    int i,length = strlen(T);
    next[0] = length;
    for(i = 0; i<length-1 && T[i]==T[i+1]; i++);
    next[1] = i;
    int a = 1;
    for(int k = 2; k < length; k++) {
        int p = a+next[a]-1, L = next[k-a];
        if( (k-1)+L >= p ) {
            int j = (p-k+1)>0? (p-k+1) : 0;
            while(k+j<length && T[k+j]==T[j]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较
            next[k] = j, a = k;
        } else next[k] = L;
    }
}
void getextand(char *S,char *T) {
    memset(next,0,sizeof(next));
    getnext(T);
    int Slen = strlen(S), Tlen = strlen(T), a = 0;
    int MinLen = Slen>Tlen?Tlen:Slen;
    while(a<MinLen && S[a]==T[a]) a++;
    extand[0] = a, a = 0;
    for(int k = 1; k < Slen; k++) {
        int p = a+extand[a]-1, L = next[k-a];
        if( (k-1)+L >= p ) {
            int j = (p-k+1)>0? (p-k+1) : 0;
            while(k+j<Slen && j<Tlen && S[k+j]==T[j] ) j++;
            extand[k] = j;
            a = k;
        } else extand[k] = L;
    }
}
int main() {
    char s[N],t[N];
    while(~scanf("%s %s",s,t)) {
        getextand(s,t);
        for(int i = 0; i < strlen(t); i++)
            printf("%d ",next[i]);
        puts("");
        for(int i = 0; i < strlen(s); i++)
            printf("%d ",extand[i]);
        puts("");
    }
}
/*
aaaabaaa aaaa
*/

整体二分

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
 /*
区间第K小
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 220000
#define inf 1000000000
using namespace std;
struct query
{
    int x,y,k,s,tp,cur;
}q[maxn],q1[maxn],q2[maxn];
int a[maxn],ans[maxn],tmp[maxn],t[maxn];
int n,m,num,cnt;
void add(int x,int y)
{
    for (int i=x;i<=n;i+=(i&-i)) t[i]+=y;
}
int ask(int x)
{
    int tmp=0;
    for (int i=x;i>0;i-=(i&-i)) tmp+=t[i];
    return tmp;
}
void divide(int head,int tail,int l,int r)
{
    //cout<<head<<' '<<tail<<' '<<l<<' '<<r<<endl;
    if (head>tail) return ;
    if (l==r) 
    {
        for (int i=head;i<=tail;i++)
            if (q[i].tp==3) ans[q[i].s]=l;//,cout<<l<<endl;
        return ;
    }
    int mid=(l+r)>>1;
    for (int i=head;i<=tail;i++)
    {
        if (q[i].tp==1&&q[i].y<=mid) add(q[i].x,1);
        else
        if (q[i].tp==2&&q[i].y<=mid) add(q[i].x,-1);
        else
        if (q[i].tp==3) tmp[i]=ask(q[i].y)-ask(q[i].x-1);
    }
    for (int i=head;i<=tail;i++)
    {
        if (q[i].tp==1&&q[i].y<=mid) add(q[i].x,-1);
        else
        if (q[i].tp==2&&q[i].y<=mid) add(q[i].x,1);
    }
    int l1=0,l2=0;
    for (int i=head;i<=tail;i++)
        if (q[i].tp==3)
        {
            if (q[i].cur+tmp[i]>q[i].k-1)//q[i].cur+tmp[i]表示累积了多少个数
                q1[++l1]=q[i];
            else
            {
                q[i].cur+=tmp[i];
                q2[++l2]=q[i];
            }
        }
        else
        {
            if (q[i].y<=mid) q1[++l1]=q[i];
            else q2[++l2]=q[i];
        }
    for (int i=1;i<=l1;i++) q[head+i-1]=q1[i];
    for (int i=1;i<=l2;i++) q[head+l1+i-1]=q2[i];
    divide(head,head+l1-1,l,mid);
    divide(head+l1,tail,mid+1,r);
}    
int main()
{
    //freopen("ranking.in","r",stdin);
    //freopen("ranking.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        q[++num].x=i; q[num].y=a[i];
        q[num].tp=1; q[num].s=0;
    }
    char sign;
    int x,y,z;
    for (int i=1;i<=m;i++)
    {
        scanf("\n%c",&sign);
        if (sign=='Q')
        {
            scanf("%d%d%d",&x,&y,&z);
            q[++num].x=x,q[num].y=y,q[num].k=z;
            q[num].tp=3; q[num].s=++cnt;
        }
        else
        {
            scanf("%d%d",&x,&y);
            q[++num].x=x; q[num].y=a[x]; 
            q[num].tp=2; q[num].s=0;
            q[++num].x=x; q[num].y=y;
            q[num].tp=1; q[num].s=0;
            a[x]=y;
        }
    }
    divide(1,num,0,inf);
    for (int i=1;i<=cnt;i++)
        printf("%d\n",ans[i]);
    return 0;
}
//不带修改区间第k小
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 200010
struct query{
    int x,y,k,id,ty;
}q[maxn],q1[maxn],q2[maxn];
int ans[maxn];
int V[maxn],len,C[maxn],n;
int lowbit(int x){
    return x&-x;
}
int sum(int x){
    int ans=0;
    while(x){
        ans+=C[x];
        x-=lowbit(x);
    }
    return ans;
}
void add(int x,int v){
    while(x<=n){
        C[x]+=v;
        x+=lowbit(x);
    }
}
void divide(int L,int R,int le,int ri){
    if(L>R) return;
    if(le==ri){
        for(int i=L;i<=R;i++)
            if(q[i].ty) ans[q[i].id]=le;
        return;
    }
    int M=(le+ri)/2;
    int a=0,b=0;
    for(int i=L;i<=R;i++){
        if(!q[i].ty){
            if(q[i].y<=M){
                add(q[i].x,1);
                q1[a++]=q[i];
            }else{
                q2[b++]=q[i];
            }
        }else{
            int tem=sum(q[i].y)-sum(q[i].x-1);
            if(tem>=q[i].k){
                q1[a++]=q[i];
            }else{
                q[i].k-=tem;
                q2[b++]=q[i];
            }
        }
    }
    for(int i=L;i<=R;i++)
        if(!q[i].ty&&q[i].y<=M) add(q[i].x,-1);
    for(int i=L;i<L+a;i++) q[i]=q1[i-L];
    for(int i=L+a;i<=R;i++) q[i]=q2[i-L-a];
    divide(L,L+a-1,le,M);
    divide(L+a,R,M+1,ri);
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i].y);
        V[len++]=q[i].y;
        q[i].x=i+1;q[i].ty=0;
    }
    sort(V,V+len);
    len=unique(V,V+len)-V;
    for(int i=0;i<n;i++)
        q[i].y=lower_bound(V,V+len,q[i].y)-V+1;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&q[n+i].x,&q[n+i].y,&q[n+i].k);
        q[n+i].id=i;q[n+i].ty=1;
    }
    divide(0,n+m-1,1,len);
    for(int i=0;i<m;i++)
        printf("%d\n",V[ans[i]-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
 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 1010
int getmin(char *s) {
    int n=strlen(s);
    int i=0,j=1,k=0,t;
    while(i<n && j<n && k<n) {
        t=s[(i+k)%n]-s[(j+k)%n];
        if (!t) k++;
        else {
            if (t>0) i+=k+1;
            else j+=k+1;
            if (i==j) j++;
            k=0;
        }
    }
    return i<j?i:j;
}
char s[maxn];
int main() {
    scanf("%s",s);
    printf("%d\n",getmin(s));
    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
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
#define maxnode 4000010
#define sigma_size 66
struct node{
    char c;
    int next,right;
    int sum;
};
ll res=0;
struct Trie{
    node T[maxnode];
    int sz;
    void init(){
        sz=1;res=0;
        T[0].next=T[0].right=-1;
        T[0].sum=0;
    }
    void insert(char *s){
        int u=0;
        for(int i=0;!i||s[i-1]!='\0';i++){
            bool flag=true;
            for(int j=T[u].next;j!=-1;j=T[j].right){
                if(T[j].c==s[i]){
                    res+=(s[i]=='\0'?1:2)*T[j].sum;
                    T[j].sum++;
                    flag=false;
                    u=j;
                    break;
                }
            }
            if(flag){
                T[sz].c=s[i];
                T[sz].right=T[u].next;
                T[sz].next=-1;
                T[sz].sum=1;
                T[u].next=sz;
                u=sz++;
            }
        }
    }
};
Trie T;
int main(){
    int n,kase=0;
    while(scanf("%d",&n)!=EOF&&n){
        T.init();
        for(int i=0;i<n;i++){
            char s[1010];
            scanf("%s",s);
            T.insert(s);
        }
        printf("Case %d: %lld\n",++kase,res+n*(n-1)/2);
    }
    return 0;
}