Posted on | In

7.13 区间dp

https://ac.nowcoder.com/acm/problem/20252

字符串最长50，求压缩后的最短长度。

这题的关键在于M。如果只有R，那么就是基础的区间dp，每次可以压缩时令dp(l,r) = min(dp(l,r), dp(l,mid)+1)，三重循环搞定。多出了规定“M”改变了什么呢？首先是每组压缩前要多一个字母，其次，如果[l, mid]中有M，那么它是不可以和[mid+1,r]合并的，这是因为题设中末尾的R会优先匹配距离它近的M，而不是l之前的M。

所以我们每处dp要记录两个值，令dp[l][r][0]表示[l, r]中不出现M的情况下，最短的压缩长度；dp[l][r][1]则表示允许出现M时的最短长度。这样一来当我们执行压缩时用的是dp[l][r][0]，而在普通的拆区间时用的是dp[l][r][1]。另外，我们只需要在每次拆区间时加上中间的那个M即可，因为最初的M省略了，M只可能在区间中出现。

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

const int maxn=54;

char s[maxn];

int dp[maxn][maxn][2];

inline bool check(int l,int len){
    for(int i=0;i<len/2;i++){
        if(s[l+i]!=s[l+len/2+i]){
            return 0;
        }
    }
    return 1;

}

int main(){
    cin>>(s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            dp[i][j][0]=dp[i][j][1]=j-i+1;
    }
    for(int len=1;len<=n;len++){
        for(int i=1,r;i+len-1<=n;i++){
            r=i+len-1;
            if(len%2==0&&check(i,len)){
                dp[i][r][0]=min(dp[i][r][0],dp[i][(i+r)/2][0]+1);
            }
            for(int j=i;j<r;j++){
                dp[i][r][0]=min(dp[i][r][0],dp[i][j][0]+r-j);
            }
            for(int j=i;j<r;j++){
                dp[i][r][1]=min(dp[i][r][1],dp[i][j][1]+1+dp[j+1][r][1]);
            }
            dp[i][r][1]=min(dp[i][r][0], dp[i][r][1]);
        }
    }
    cout<<dp[1][n][1]<<endl;
}

Posted on | In

四边形不等式

1d1d

即dp数组一维，筛选判优一个dp值花费一维时间

对于形如dp[i]=min(dp[k]+w(k+1,i))，1<=k<i 的转移式，可以证明如果i>j那么dp[i]的最优决策点比dp[j]的最优决策点大https://oi-wiki.org/dp/opt/quadrangle/，那么此时我们不像2d1d中，可以对当前dp分界点设置上下界，我们只能得到一个单侧的界限，比如已经知道dp[i]的最优分界点在m处，那么下标大于i的dp值的分界点都不小于m，这样就不能减少一维，而是把n变log，模板如下，大概就是每次算出中间位置的dp，然后两侧dp的可枚举区间就少了一半。

1
2
3
4
5
6
7
8
9
10
void DP(int l, int r, int k_l, int k_r) {
  int mid = (l + r) / 2, k = k_l;
  // 求状态f[mid]的最优决策点
  for (int i = k_l; i <= min(k_r, mid - 1); ++i)
    if (w(i, mid) < w(k, mid)) k = i;
  f[mid] = w(k, mid);
  // 根据决策单调性得出左右两部分的决策区间，递归处理
  if (l < mid) DP(l, mid - 1, k_l, k);
  if (r > mid) DP(mid + 1, r, k, k_r);
}

例题：https://codeforces.com/problemset/problem/321/E

这题其实有人用2d1d的做法……不过我没证明正确性，还是老老实实用可证实的方法。复杂度knlogn

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

const int maxn=4002;
const int maxk=802;
#define inf 0x3f3f3f3f

int sum[maxn][maxn],w[maxn][maxn],dp[maxk][maxn];
inline int read(){
	int v=0, f=1;
	char c=getchar();
	while(c<48||57<c){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(48<=c&&c<=57)
		v=v*10+c-48, c=getchar();
	return v*f;
}

void solve(int f[],int g[],int l,int r,int pos_l,int pos_r){
    int mid=(l+r)>>1,res=pos_l;
    g[mid]=inf;
    for(int i=pos_l;i<=min(mid-1,pos_r);i++){
        if(f[i]+w[i+1][mid]<g[mid]){
            g[mid]=f[i]+w[i+1][mid];
            res=i;
        }
    }
    if(l<mid)
        solve(f,g,l,mid-1,pos_l,res);
    if(r>mid)
        solve(f,g,mid+1,r,res,pos_r);
}

int main(){
    int n=read(),k=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            sum[i][j]=sum[i][j-1]+read();
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            w[i][j]=w[i][j-1]+sum[j][j-1]-sum[j][i-1];
        }
    }
    for(int i=1;i<=n;i++){
        dp[1][i]=w[1][i];
    }
    for(int i=2;i<=k;i++)
        solve(dp[i-1],dp[i],i,n,i-1,n-1);
    cout<<dp[k][n]<<endl;
}

Posted on | In

题目链接 https://ac.nowcoder.com/acm/problem/14254

题目大意：给一个二分图（n<=1e3，m<=2e3），要求对它的边进行染色，相邻边（即有公共点的边）不能是同一种颜色，问最少用多少种颜色（k）能完成染色任务，并输出一组可行解（每条边的颜色为1~k间的数）。

在图论中有一个Vizing定理：二分图边着色所需最小颜色数，等于图中点的最大度数。我们设当前需要在u和v之间加一条边，设u点尚未用过的最小的颜色编号是x，v点尚未用过的最小颜色编号是y。那么如果x=y，就直接令边(u,v)的颜色是x（y）即可；如果x<y，我们依然令(u,v)的颜色是x，然后让点v原有的颜色为x的边变色为y，接下来对于这条边连接的点v’，让它原有的颜色为y的边再变色为x……就这样一直修改下去，修改路径是一条从v出发，颜色依次是x、y、x……的边构成的路径（不会经过u）。
修改这条增广路的操作可以用dfs实现，复杂度是O（n）。在添加每条边的时候都有可能需要修改，所以整体复杂度O（mn）。

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;

const int maxn=1001;

int es[maxn][maxn];
int color[maxn<<1];
typedef pair<int,int> pir;
map<pir,int> mp;

void dfs(int u,int v,int x,int y){
    int to=es[v][x];
    //把uv边从y色染成x色
    es[u][x]=v;es[v][x]=u;
    if(!to){
        //如果v之前没有x色的边
        es[v][y]=0;
    }else{
        dfs(v,to,y,x);
    }
}

int main(){
    int n,m,cur[2];
    cin>>n>>m;
    int ans=0;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        mp[pir(u,v)]=i;
        mp[pir(v,u)]=i;
        cur[0]=cur[1]=1;
        while(es[u][cur[0]])
            cur[0]++;
        while(es[v][cur[1]])
            cur[1]++;
        if(cur[0]>cur[1]){
            swap(u,v);swap(cur[0],cur[1]);
        }
        ans=max(ans,cur[1]);
        if(cur[0]==cur[1]){
            es[u][cur[0]]=v;
            es[v][cur[0]]=u;
        }else{
            dfs(u,v,cur[0],cur[1]);
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=ans;j++){
            int v=es[i][j];
            if(v){
                color[mp[pir(i,v)]]=j;
            }
        }
    }
    for(int i=1;i<=m;i++)
        cout<<color[i]<<endl;
}

/*
5 4
1 2
1 3
1 4
4 5
*/

Posted on | In

https://codeforces.com/contest/160/problem/D

众所周知连通图的mst可能有多个，现给定一个无向图（n、m<=1e5），要求判断每条边，是存在于所有的mst中，还是至少存在于一个mst中，还是不存在于任一mst中。

我们现在来考虑Kruskal的算法流程，首先对于边按权值排序，从小到大挨个添加（当两个端点不连通时）。当我们遇到若干条权值相同的边，且都满足添加条件时，则可以任选一条，这就是1、2的情况。而如果当前边的两端已经在同一点集中，这条边则不可能被添加，是第三种情况。接下来我们考虑如何区分前两种情况。

首先对于若干条相等的边，如果判断它可以连，就先把对应点集的祖先连接在一起，点集暂时不合并。就这样处理完之后，我们在当前图找桥，复杂度O（刚添加的边数）。桥边属于必选，剩下的边则是可选。然后第三步，则是把这些边两端的点集都合并起来，并把之前的连边信息清空，因为他们现在属于一个点集了，有公共的祖先，就不需要这些内部边了。这里所用到的一个技巧就是，用每个点集的祖先代表这个点集中的所有点，如果一个点集向另一个点集发出两条边，则相当于这两个祖先点连了两条重边，则这两条边都是可选；如果只有一条，那么就必须选择。然后这里的找桥算法也需要修改，为了支持重边的情况，之前算法中是不采用来自父亲的边，现在修改为不采用通向当前点u的这条边，其余通向父亲的重边是可以采用的。这样一来就不会误判桥了。

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

const int maxn=1e5+4;

struct d{
    int u,v,w,pos;
    friend bool operator<(d x,d y){
        return x.w<y.w;
    }
}ds[maxn];

struct edge{
    int to,next;
    int pos;
}es[maxn<<1];
int head[maxn],cnt;
inline void add(int u,int v,int pos){
    es[++cnt]=(edge){ v,head[u],pos};
    head[u]=cnt;
}

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

int ans[maxn];
int dfn[maxn],low[maxn],dcnt;
void tarjan(int u,int from){
    //这里from是边的编号(正反边是用同一个编号)，否则多排除掉一些重边（有的话）
    dfn[u]=low[u]=++dcnt;
    for(int i=head[u];i;i=es[i].next){
        int v=es[i].to;
        if(!dfn[v]){
            tarjan(v,es[i].pos);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                ans[es[i].pos]=2;
            }
        }else if(from!=es[i].pos){
            low[u]=min(low[u],dfn[v]);
        }
    }
}
void merge(int a,int b){
    int A=find(a),B=find(b);
    if(A!=B){
        head[a]=head[b]=head[A]=head[B]=0;
        dfn[a]=dfn[b]=dfn[A]=dfn[B]=0;
        low[a]=dfn[b]=dfn[A]=dfn[B]=0;
        fa[A]=B;
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    memset(head,0,sizeof(int)*(n+1));
    for(int i=1;i<=m;i++){
        cin>>ds[i].u>>ds[i].v>>ds[i].w;
        ds[i].pos=i;
    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    sort(ds+1,ds+1+m);
    for(int i=1;i<=m;i++){
        int ss=i,ee=i;
        while(ee<m&&ds[ee+1].w==ds[ss].w)
            ee++;
        for(int j=ss;j<=ee;j++){
            int fu=find(ds[j].u);
            int fv=find(ds[j].v);
            if(fu!=fv){
                ans[ds[j].pos]=1;
                add(fu,fv,ds[j].pos);
                add(fv,fu,ds[j].pos);
            }
        }
        for(int j=ss;j<=ee;j++){
            int fu=find(ds[j].u);
            int fv=find(ds[j].v);
            if(!dfn[fu]&&fu!=fv)
                tarjan(fu,-1);
            if(!dfn[fv]&&fu!=fv)
                tarjan(fv,-1);
        }
        for(int j=ss;j<=ee;j++){
            merge(find(ds[j].u),find(ds[j].v));
        }
        i=ee;
    }
    for(int i=1;i<=m;i++){
        switch(ans[i]){
            case 0:
                cout<<"none"<<endl;
                break;
            case 1:
                cout<<"at least one"<<endl;
                break;
            case 2:
                cout<<"any"<<endl;
                break;
        }
    }
}

Posted on | In

https://codeforces.com/contest/1373/problem/F

这题感觉出的很棒，感觉很简洁经典的题面，却从未见过（可能是做题太少）。

有环形的n个城市、n个资源站交替排布，每个城市需要资源ai，每个资源站最多能提供资源bi（只能给它两侧的城市ai、ai+1提供）。问能这n个城市的需求能否得到满足。1e6

这题一看很明显就知道能通过某种很妙的算法扫一遍就行，但比赛中想不到（；´д｀）ゞ。后来题解出来瞟了一眼就瞬间明白。

首先我们从任意位置开始向右扫，在满足必须需求need的基础上把bi都给右侧；必要需求是什么呢？就是当前bi左侧的ai剩余未满足的部分，这部分是一定要由bi向左补足的，因为我们bi的给予从一开始是优先向右，等于牺牲了a1，如果这样的条件下ai都不能被满足，那么就不会有成功的情况了。同时我们需要维护最多能“回流”多少资源res，这是因为对于有的bi，可能在满足左侧必要需求，并把右侧ai+1，全部满足之后还有剩余，那么就可以考虑把它向左回流，减轻bi-1的负担，这样一路回流到a1。然后我们执行完bn后，这时已计算出a1（n+1）的need，然后比较，如果res>=need的话就成功，这表明我们在满足a2-n都满足的情况下，能够向左返还给b1、使得b1能向左分配的资源，比给a1提供bn资源后剩下未满足的部分要多或等于，即所有a全部满足。

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

const int maxn=1e6+4;

#define ll long long

ll a[maxn],b[maxn];

int main(){
    std::ios::sync_with_stdio(false);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        a[n+1]=a[1];
        bool ans=true;
        ll need=0,res=0,add=0,extra=2e9;
        for(int i=1;i<=n;i++){
            if(b[i]<need){
                ans=false;
                break;
            }
            b[i]-=need;
            extra=min(extra,a[i]-need);
            if(b[i]>a[i+1]){
                ll left=b[i]-a[i+1];
                add=min(extra,left);
                extra-=add;
                res+=add;
                need=0;
            }else{
                need=a[i+1]-b[i];
            }
        }
        ans=ans&(res>=need);
        cout<<(ans?"YES":"NO")<<endl;
    }
}

Posted on | In

最长平稳上升子序列

https://codeforces.com/contest/1367/problem/F2

对于一个序列定义这样一种操作：取出任意一个数，放在数列最前面或者最后面。求最少操作多少次可以让序列变得有序。数字有可能重复，2e5。

简单思考后我们发现，其实就是需要我们找到最长的、平稳上升（相邻数字增加1或相同）的子序列，这样的序列可以不用动，只需要把应该位于它两侧的数字取出并放在它两侧即可，所以最少操作次数=n-maxlen。

最长平稳上升子序列（以下简称子序列）的构成遵循这样的特征：位于中间段的数字必须包括数列中全部的该数字，而位于两侧的数字则可以只是一部分，例如24324，234满足要求。这样一来dp就分为两部分，我们先求出整块的数字能构成的最长子序列，然后对于两侧加上所有能加的首尾元素，这个直接对元素的位置用lower_bound即可。

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

const int maxn=2e5+4;

int t,n,a[maxn],_a[maxn];
int dp[maxn],l[maxn],r[maxn],start[maxn];   //整块的大小、某值左界、某值右界、某值整块的左界
vector<int> pos[maxn];

int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            _a[i]=a[i];
        }
        sort(_a+1,_a+1+n);
        int tot=unique(_a+1,_a+1+n)-_a-1;
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(_a+1,_a+1+tot,a[i])-_a;
        }
        memset(dp+1,0,sizeof(int)*n);
        for(int i=1;i<=tot;i++)
            pos[i].clear();
        for(int i=1;i<=n;i++){
            pos[a[i]].push_back(i);
        }
        for(int i=1;i<=tot;i++){
            sort(pos[i].begin(),pos[i].end());
            l[i]=pos[i][0];r[i]=*pos[i].rbegin();
        }
        for(int i=1;i<=tot;i++){
            if(l[i]>r[i-1]){
                dp[r[i]]=dp[r[i-1]]+pos[i].size();
                start[i]=start[i-1];
            }else{
                dp[r[i]]=pos[i].size();
                start[i]=l[i];
            }
        }
        int ans=0;
        for(int res,i=1;i<=n;i++){
            res=0;
            if(dp[i]){
                int j=start[a[i]];
                int L=a[j],R=a[i];
                res+=dp[i];
                if(L>1)
                    res+=upper_bound(pos[L-1].begin(),pos[L-1].end(),j-1)-pos[L-1].begin();
                if(R<tot)
                    res+=pos[R+1].end()-lower_bound(pos[R+1].begin(),pos[R+1].end(),i+1);
            }else{
                int L=a[i],R=a[i]+1;
                res+=upper_bound(pos[L].begin(),pos[L].end(),i)-pos[L].begin();
                if(R<=tot)
                    res+=pos[R].end()-lower_bound(pos[R].begin(),pos[R].end(),i+1);
            }
            ans=max(ans,res);
        }
        cout<<n-ans<<endl;
    }
}

Posted on | In

基本平衡树操作

splay的旋转x，就是把它和fa[x]在不违反定义的情况下互换父子关系，左儿子变左父亲，例如。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+2;
int cnt[maxn],ch[maxn][2],fa[maxn],val[maxn],sz[maxn],rt,tot;

struct Splay{
    void clear(int x){
        ch[x][0]=ch[x][1]=fa[x]=sz[x]=cnt[x]=0;
    }
    void pushup(int x){
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
    }
    bool get(int x){
        return x==ch[fa[x]][1];
    }
    void rotate(int x){ //在不破坏二叉搜索性条件下改变x父子关系
        int y=fa[x],z=fa[y],chk=get(x);
        ch[y][chk]=ch[x][chk^1];
        fa[ch[x][chk^1]]=y;
        ch[x][chk^1]=y;
        fa[y]=x;
        if(z) ch[z][y==ch[z][1]]=x;
        fa[x]=z;
        pushup(y);
        pushup(x);
    }
    void splay(int x){
        for(int f=fa[x];f=fa[x],f;rotate(x)){
            if(fa[f])
                rotate(get(x)==get(f)?f:x);
        }
        rt=x;
    }
    void ins(int k){
        if(!rt){
            val[++tot]=k;
            cnt[tot]++;
            rt=tot;
            pushup(rt);
            return;
        }
        int cur=rt,f=0;
        while(1){
            if(val[cur]==k){
                cnt[cur]++;
                pushup(cur);
                pushup(f);
                splay(cur);
                break;
            }
            f=cur;
            cur=ch[cur][val[cur]<k];
            if(!cur){
                val[++tot]=k;
                cnt[tot]++;
                fa[tot]=f;
                ch[f][val[f]<k]=tot;
                pushup(tot);
                pushup(f);
                splay(tot);
                break;
            }
        }
    }
    //查x的排名
    int rk(int x){
        int res=0,cur=rt;
        while(1){
            if(x<val[cur]){
                cur=ch[cur][0];
            }else{
                res+=sz[ch[cur][0]];
                if(x==val[cur]){
                    splay(cur);
                    return res+1;
                }
                res+=cnt[cur];
                cur=ch[cur][1];
            }
        }
        return res;
    }
    //查排名k的数
    int kth(int k){
        int cur=rt;
        while(1){
            if(ch[cur][0]&&k<=sz[ch[cur][0]])
                cur=ch[cur][0];
            else{
                k-=cnt[cur]+sz[ch[cur][0]];
                if(k<=0){
                    splay(cur);
                    return val[cur];
                }
                cur=ch[cur][1];
            }
        }
    }
    //查x的前驱编号，先插入x，再pre()，再删除x
    int pre(){
        //找x左子树中最大节点
        int cur=ch[rt][0];
        while(ch[cur][1])
            cur=ch[cur][1];
        splay(cur);
        return cur;
    }
    int nxt(){
        int cur=ch[rt][1];
        while(ch[cur][0])
            cur=ch[cur][0];
        splay(cur);
        return cur;
    }

    void del(int k){
        rk(k);
        if(cnt[rt]>1){
            cnt[rt]--;
            pushup(rt);
            return;
        }
        if(!ch[rt][0]&&!ch[rt][1]){
            clear(rt);
            rt=0;
            return;
        }
        if(!ch[rt][0]){
            int cur=rt;
            rt=ch[cur][1];
            fa[rt]=0;
            clear(cur);
            return;
        }
        if(!ch[rt][1]){
            int cur=rt;
            rt=ch[cur][0];
            fa[rt]=0;
            clear(cur);
            return;
        }
        int cur=rt,x=pre();
        splay(x);
        fa[ch[cur][1]]=x;
        ch[x][1]=ch[cur][1];
        clear(cur);
        pushup(rt);
    }
}tree;


int main(){
    int n;
    cin>>n;
    for(int i=1,opt,x;i<=n;i++){
        cin>>opt>>x;
        switch(opt){
        case 1:
            tree.ins(x);
            break;
        case 2:
            tree.del(x);
            break;
        case 3:
            cout<<tree.rk(x)<<endl;
            break;
        case 4:
            cout<<tree.kth(x)<<endl;
            break;
        case 5:
            tree.ins(x);
            cout<<val[tree.pre()]<<endl;
            tree.del(x);
            break;
        case 6:
            tree.ins(x);
            cout<<val[tree.nxt()]<<endl;
            tree.del(x);
            break;
        default:
            ;
        }
    }
}

做区间翻转

由于splay操作可以将任一节点在不违反定义的情形下移动到根，splay树由此多了一些用途，例如维护区间翻转。

https://www.luogu.com.cn/problem/P3391

对于splay操作稍作修改，可以使得某节点上升至任一位置。

然后我们用原序列的下标建树。需要翻转某个区间时，先将l-1splay到根的位置，再将r+1splay到根的右儿子上，现在r+1的左儿子就是要翻转的区间。

对于一棵树，翻转区间就是从上而下交换每个节点的左右儿子，可以打lazy标记，实现log复杂度。

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

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar();}
    return x*f;
}

const int maxn=1e5+2;
#define lson (ch[o][0])
#define rson (ch[o][1])
int ch[maxn][2],rev[maxn],size[maxn],fa[maxn],val[maxn],rt,n,m;

void pushup(int o){
    size[o]=size[lson]+size[rson]+1;
}
void pushdown(int o){
    if(rev[o]){
        swap(lson,rson);
        rev[lson]^=1;rev[rson]^=1;rev[o]=0;
    }
}

void build(int l,int r,int o){
    if(l>r)
        return;
    int mid=(l+r)>>1;
    if(mid<o){
        lson=mid;
    }else{
        rson=mid;
    }
    fa[mid]=o;size[mid]=1;
    if(l==r)
        return;
    build(l,mid-1,mid);
    build(mid+1,r,mid);
    pushup(mid);
}

bool get(int x){
    return x==ch[fa[x]][1];
}
void rotate(int x){ //在不破坏二叉搜索性条件下改变x父子关系
    int y=fa[x],z=fa[y],chk=get(x);
    pushdown(y);
    pushdown(x);
    ch[y][chk]=ch[x][chk^1];
    fa[ch[x][chk^1]]=y;
    ch[x][chk^1]=y;
    fa[y]=x;
    if(z) ch[z][y==ch[z][1]]=x;
    fa[x]=z;
    pushup(y);
    pushup(x);
}
void splay(int x,int goal){	//goal是目标位置的父亲
    for(int f;f=fa[x],f!=goal;rotate(x)){
        if(fa[f]!=goal)
            rotate(get(x)==get(f)?f:x);
    }
    if(goal==0)
        rt=x;
}

int find(int k,int o){
    pushdown(o);
    if(k==size[lson]+1){
        return o;
    }else if(k<=size[lson]){
        return find(k,lson);
    }else{
        return find(k-(size[lson]+1),rson);
    }
}

void reverse(int L,int R){
    splay(L,0);
    splay(R,rt);
    rev[ch[R][0]]^=1;
}

void print(int o){
    pushdown(o);
    if(lson)
        print(lson);
    if(val[o]&&val[o]<=n)
        printf("%d ",val[o]);
    if(rson)
        print(rson);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n+2;i++)
        val[i]=i-1;
    rt=(n+3)>>1;
    build(1,n+2,rt);
    fa[rt]=0;	//build在根的处理上重复了一次，要重新把根的父节点设为0，要不splay会无法停止
    for(int i=1,l,r;i<=m;i++){
        cin>>l>>r;
        int L=find(l,rt);
        int R=find(r+2,rt);
        reverse(L,R);
    }
    print(rt);
}

Posted on | In

参考：笛卡尔树学习笔记 - 作业部落 Cmd Markdown 编辑阅读器

笛卡尔树是一种二叉树，每个节点维护两个值，一个是需要满足二叉搜索树性质的val，另一个是需要满足堆性质的priority。

在val排好序的情况下，笛卡尔树可以在线性时间内构建。一个有用的结论是，对于一组固定的节点，构造出的笛卡尔树是唯一的。

例如下图中，数组下标是val，元素值是priority

image

构建方法很简单，先将节点按照val排序，然后挨个从右边插入（这就是为什么代码中r[0]的值也是rt），同时用单调栈维护右链（递增或递减），然后插入节点时弹出的链变为节点的左子树，再将节点连在右链下。

http://poj.org/problem?id=1785

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
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<assert.h>
using namespace std;

const int maxn=5e4+2;

struct node{
    string label;
    int pri;
    friend bool operator<(node x,node y){
        return x.label<y.label;
    }
}ns[maxn];

int n,l[maxn],r[maxn],stk[maxn],p,rt;

void build(){
    for(int i=1;i<=n;i++){
        while(p&&ns[i].pri>ns[stk[p]].pri){
            l[i]=stk[p--];
        }
        r[stk[p]]=i;
        stk[++p]=i;
    }
    assert(r[0]==stk[1]);
    rt=stk[1];
}

void output(int o){
    putchar('(');
    if(l[o]){
        output(l[o]);
    }
    cout<<ns[o].label<<'/'<<ns[o].pri;
    if(r[o]){
        output(r[o]);
    }
    putchar(')');
}
int main(){
    while(cin>>n&&n){
        p=0;
        memset(l,0,sizeof(int)*(n+1));
        memset(r,0,sizeof(int)*(n+1));
        string label;
        int pri;
        for(int i=1;i<=n;i++){
            getchar();
            getline(cin,label,'/');
            cin>>pri;
            ns[i].label=label;
            ns[i].pri=pri;
        }
        sort(ns+1,ns+1+n);
        build();
        output(rt);
        cout<<endl;
    }
}

拓展

再看一道难一点的题https://codeforces.com/contest/1220/problem/F

官方做法是用线段树，维护每次移动后每个节点的祖先数目。然后最多的祖先数目就是树深。现在考虑怎么用笛卡尔树来做。

看博客补充了一个笛卡尔树的黑科技：在插入节点时不断维护树的高度。原理很清晰，我们维护右链上每个节点的子树的深度，在插入节点时看它冲掉了哪些右链节点，在这些节点里面取最深的+1，就是新节点子树的深度；如果一个都没有冲掉，那么该节点的位置（链长）就是它的子树深度。注意这里子树深度说的是，这个子树里最深的点在整棵树中的深度。这样一来，我们就可以维护全局最小点两侧不断插入节点后的树深。整棵树的深度就是两侧较大的再+1。枚举全局最小点应该在哪个位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;

const int maxn=2e5+2;
int n,a[maxn],val[maxn];
int ls[maxn],rs[maxn],stk[maxn],p,rt;
int dpl[maxn],dpr[maxn];

//dp记录添加某个点后子树深度，这个可以通过笛卡尔树建树搞出来，l和r分别表示在全局最小元素的左边和右边

int tmp_dep[maxn];  //表示栈中第i个元素的子树所能达到的深度
void solve_dp(int* dp){
    p=0;
    int mx=0;           //当前树高
    for(int i=1;i<n;i++){
        int tmp=0;    //当前节点能冲掉的栈中节点的子树深度，如果一个都冲不掉，那么该节点的子树深度就是它本身，即链长
        while(p&&val[i]<val[stk[p]]){
            tmp=max(tmp,tmp_dep[stk[p--]]);
        }
        stk[++p]=i;
        if(tmp==0){
            tmp_dep[i]=p;
        }else{
            tmp_dep[i]=tmp+1;   //能冲掉的最深的节点的子树深度 加上它本身
        }
        dp[i]=(mx=max(mx,tmp_dep[i]));
    }
}

int main(){
    cin>>n;
    int mn=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<a[mn]){
            mn=i;
        }
    }
    for(int i=1,j=(mn-2+n)%n+1;i<n;i++,j=(j-2+n)%n+1){
        val[i]=a[j];
    }
    solve_dp(dpl);
    for(int i=1,j=mn%n+1;i<n;i++,j=j%n+1){
        val[i]=a[j];
    }
    solve_dp(dpr);
    int res=1,ans=2e9;
    for(int i=1;i<=n;i++){
        if(max(dpl[i-1],dpr[n-i])+1<ans){
            res=i;
            ans=max(dpl[i-1],dpr[n-i])+1;
        }
    }
    cout<<ans<<' '<<(mn+n-res)%n<<endl;
}

Posted on | In

这题真的长见识了哈哈

https://codeforces.com/contest/1363/problem/F

给字符串s、t，可对s进行局部右旋操作，求将s转变成t的最小操作数。

经过分析我们发现，右旋的本质是将右边的某个字符挪到左边。我们从后往前尝试满足t字符串的匹配。例如首先看s[n]是否等于t[n]，如果不相等，将s[n]拿起来准备插入前面的某个位置，注意这时它处于“悬而未决”状态，接下来我们不断前移s的指针i去匹配t的后缀直至全部匹配，每次都尝试三种情况：

直接把s[i]拿起、i–，花费++

如果s[i]=t[j]则直接匹配，双方指针都向前挪动、

如果悬而未决的元素中有能匹配t[j]的，则用它去匹配，然后j–，这个判断需要记录字符的后缀和。

然后我们令dp[i][j]表示从两个指针分别等于i和j时开始到整个匹配过程结束所需的花费，根据前述三种情况，这个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
#include<bits/stdc++.h>
using namespace std;

const int maxn=2002;

int T,n;
char s[maxn],t[maxn];
int cache[maxn][maxn];
int sufs[maxn][26],suft[maxn][26];

int dp(int i,int j){
    //dp(i,j)的含义是：t[j+1..n]后缀已经得到匹配的情形下，用s[1..i]以及悬而未决的j-i个元素依次匹配t[j]..t[1]的最小花费
    //悬而未决的元素可以放在任何位置，所以dp[0][j]=0，这时s已经没有可拿起的元素，直接把悬而未决的元素按照t[1..j]排列即可
    if(~cache[i][j])
        return cache[i][j];
    int res=2e9;
    if(i){
        res=1+dp(i-1,j);
        if(s[i]==t[j]){
            res=min(res,dp(i-1,j-1));
        }
        int ch=t[j]-'a';
        if(sufs[i+1][ch]>suft[j+1][ch]){
            res=min(res,dp(i,j-1));
        }
    }
    return cache[i][j]=res;
}

int main(){
    cin>>T;
    while(T--){
        cin>>n>>(s+1)>>(t+1);
        for(int j=0;j<=n;j++)
            cache[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=n;j++){
                cache[i][j]=-1;
            }
        }
        for(int i=0;i<26;i++){
            sufs[n+1][i]=0;
            suft[n+1][i]=0;
        }
        for(int i=n;i;i--){
            for(int j=0;j<26;j++){
                sufs[i][j]=sufs[i+1][j];
                suft[i][j]=suft[i+1][j];
            }
            sufs[i][(int)(s[i]-'a')]++;
            suft[i][(int)(t[i]-'a')]++;
        }
        bool f=true;
        for(int i=0;i<26;i++){
            if(sufs[1][i]!=suft[1][i]){
                f=false;
                break;
            }
        }
        int ans=(f?dp(n,n):-1);
        cout<<ans<<endl;
    }
}

还有一种做法好理解，我们设想，如果允许左旋和右旋，那么直接找到两者最长公共子序列长度len，然后n-len就是答案，因为剩余相对关系混乱的元素只需要移动一次就能排好。然鹅现在只支持右旋，所以我们在求最长公共子序列时受到限制，在+1时需要保证s右边字符都大于等于t的右边字符数，因为混乱元素只能向左移不能向右。