暑假补遗

ACM

感觉要给自己每天一定的任务，现在目标是刷图论和数据结构的题目。

进阶指南的链接

并查集

学习的教程

关押罪犯

注意这道题不要使用路径压缩，然后将集合分配到两个不同集合中也需要注意它的写法

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4+10;
struct Node{
    int u, v, w;
}node[100000+10];
int fa[maxn*2];
int find_fa(int x){
    int a = x;
    while(x!=fa[x]){
        x = fa[x];
    }
//    while(a!=fa[a]){
//        int z = a;
//        a = fa[a];
//        fa[z] = z;
//    }
    return x;
}
//int find_fa(int x)
//{
//    return x == fa[x]?x:x=find_fa(fa[x]);
//}
int n, m;
bool cmp(Node a, Node b){
    return a.w>b.w;
}
void init(){
    for(int i=1; i<=2*n; i++) fa[i] = i;
}
int main()
{
    scanf("%d%d", &n, &m);
    int u, v, w;
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &u, &v, &w);
        node[i].u = u, node[i].v = v, node[i].w=w;
    }
    sort(node+1, node+m+1, cmp);
    init();
    bool flag = false;
    for(int i=1; i<=m; i++){
        u=find_fa(node[i].u), v = find_fa(node[i].v), w=node[i].w;
        //cout<<node[i].u<<" "<<node[i].v<<" "<<node[i].w<<endl;
        if(u == v){
            flag = true;
            printf("%d\n", w);
            break;
        }
        //这里将集合分成两个部分很巧妙
        fa[u] = find_fa(node[i].v+n);
        fa[v] = find_fa(node[i].u+n);
    }
    if(!flag) printf("0\n");
    return 0;
}

poj移动木块

注意并查集合并的顺序，并且注意路径压缩的范围

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn = 3e4+10;
int fa[maxn], cnt[maxn], sz[maxn];
int n;
int find_fa(int x){
    if(x != fa[x]){
        //路径合并的时候，爸爸是在最底下的
        int fax = fa[x];
        fa[x] = find_fa(fa[x]);
        cnt[x] += cnt[fax];
    }
    return fa[x];
}
void init(){
    for(int i=0; i<maxn; i++) fa[i] = i, sz[i] = 1, cnt[i] = 0;
}
int main()
{
    while(~scanf("%d", &n)){
        init();
        char op;
        int u, v;
        for(int i=1; i<=n; i++){
            getchar();
            scanf("%c ", &op);
            if(op == 'M'){
                scanf("%d%d", &u, &v);
                int fau = find_fa(u);
                int fav = find_fa(v);
                //cout<<"test"<<" "<<fau<<" "<<fav<<endl;
                if(fau!=fav){
                    fa[fau] = fav;
                    cnt[fau] = sz[fav];
                    sz[fav] += sz[fau];
                }
            }
            else{
                scanf("%d", &u);
                find_fa(u);
//                cout<<"now"<<fa[3]<<endl;
//                cout<<"keke"<<cnt[4]<<" "<<u<<endl;
                printf("%d\n", cnt[u]);
            }
        }
    }
    return 0;
}

网络流

miking way

  1. 自己的二分写崩了，注意这种二分的写法
  2. 会有重边，不需要去重

ac code

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 205;
const int INF = 1e9+10;
struct Edge{
    int to, cap, rev;
};
vector<Edge> G[maxn];
int cnt[maxn];
int level[maxn];
int s, t;
int n, m, k;
void add_edge(int u, int v, int cap){
    G[u].push_back(Edge{v, cap, G[v].size()});
    G[v].push_back(Edge{u, 0, G[u].size()-1});
}
void bfs(int s){
    memset(level, -1, sizeof(level));
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    level[s] = 0;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int i=0; i<G[v].size(); i++){
            Edge& e = G[v][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to] = level[v]+1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int v, int t, int flow){
    if(v == t) return flow;
    for(int& i=cnt[v]; i<G[v].size(); i++){
        Edge& e = G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d = dfs(e.to, t, min(flow, e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;//一旦有一条路径满足就立即返回！
            }
        }
    }
    return 0;
}
int max_flow(int s, int t){
    int flow = 0;
    for(;;){
        //构造层次图
        bfs(s);
        //无法连通终点，结束访问
        if(level[t]<0) return flow;
        int f;
        //cnt数组记录在递归的过程中的边的顺序。
        memset(cnt, 0, sizeof(cnt));
        //当存在增广路的时候不断的进行增广
        while((f = dfs(s, t, INF))>0){
            flow+=f;
        }
    }
}
void init(){
    for(int i=0; i<maxn; i++) G[i].clear();
    memset(cnt, 0, sizeof(cnt));
}
int mp[40010][3];
int main()
{
    while(~scanf("%d%d%d", &n, &m, &k)){
        for(int i=0; i<=n; i++) G[i].clear();
        memset(mp, 0, sizeof(mp));
        int u, v, cap;
        int l=0, r = -1;
        for(int i=0; i<m; i++){
            scanf("%d %d %d", &u, &v, &cap);
            mp[i][0]=u, mp[i][1] = v, mp[i][2] = cap;
            r = max(r, cap);
        }
//        for(int i=1; i<=n; i++){
//            cout<<"ith number ";
//            for(int j=1; j<=n; j++){
//                if(mp[i][j]) {
//                    cout<<i<<" "<<j<<" "<<mp[i][j]<<endl;
//                }
//            }
//            cout<<endl;
//        }
        int mid;
        int res;
        while(l<=r)
        {
            mid = (l+r)/2;;
            init();
            //cout<<l<<" "<<r<<endl;
            for(int i=0; i<m; i++){
                if(mp[i][2]<=mid) add_edge(mp[i][0], mp[i][1], 1), add_edge(mp[i][1], mp[i][0], 1);
            }
            int ans = max_flow(1, n);
            //cout<<"emm "<<mid<<" "<<ans<<endl;
            if(ans>=k) r = mid-1, res = mid;
            else l = mid+1;
        }
        printf("%d\n", res);
    }
    return 0;
}

线段树

单点更新，区间查询

区间更新，区间、单点查询

扫描线

hdu 1542

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
/*
POJ 1151 Atlantis
求矩形并的面积（线段树+离散化）
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
const int maxn = 205;
struct Node
{
    //int l,r;//线段树的左右整点
    int c;//c用来记录重叠情况
    double cnt,lf,rf;//
    //cnt用来计算实在的长度，rf,lf分别是对应的左右真实的浮点数端点
}node[maxn<<2];
struct Line
{
    double x,y1,y2;
    int f;
}line[maxn];
//把一段段平行于y轴的线段表示成数组 ，
//x是线段的x坐标，y1,y2线段对应的下端点和上端点的坐标
//一个矩形 ，左边的那条边f为1，右边的为-1，
//用来记录重叠情况，可以根据这个来计算，nod节点中的c
bool cmp(Line a,Line b)//sort排序的函数
{
    return a.x < b.x;
}
double y[maxn];//记录y坐标的数组
void Build(int rt,int l,int r)//构造线段树
{
    //segTree[t].l=l;segTree[t].r=r;
    node[rt].cnt=node[rt].c=0;
    node[rt].lf=y[l];
    node[rt].rf=y[r];
    if(l+1 == r)  return;
    Build(ls, l, mid);
    Build(rs, mid, r);//递归构造,为mid，不为mid+1
}
void calen(int rt, int l, int r)//计算长度
{
    if(node[rt].c>0)
    {
        node[rt].cnt=node[rt].rf - node[rt].lf;
        return;
    }
    if(l == r)  node[rt].cnt=0;
    else  node[rt].cnt=node[ls].cnt+node[rs].cnt;
}
void update(int rt,Line e, int l ,int r)//加入线段e，后更新线段树
{
    if(e.y1<=node[rt].lf&&e.y2>=node[rt].rf)
    {
        node[rt].c+=e.f;
        calen(rt, l, r);
        return;
    }
    if(e.y2<=node[ls].rf)  update(ls, e, l, mid);
    else if(e.y1>=node[rs].lf)  update(rs, e, mid, r);
    else
    {
        Line tmp=e;
        //tmp.y2=segTree[t<<1].rf;
        update(ls,tmp, l, mid);
        //tmp=e;
        //tmp.y1=segTree[t<<1|1].lf;
        update(rs,tmp, mid, r);
    }
    calen(rt, l, r);
}
int main()
{
    int i,n,t,iCase=0;
    double x1,y1,x2,y2;
    while(scanf("%d",&n),n)
    {
        iCase++;
        t=1;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[t].x=x1;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=1;
            y[t]=y1;
            t++;
            line[t].x=x2;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=-1;
            y[t]=y2;
            t++;
        }
        sort(line+1,line+t,cmp);
        sort(y+1,y+t);
//        for(int i=1; i<t; i++){
//            cout<<"haha "<<line[i].f<<" "<<line[i].x<<" "<<line[i].y1<<" "<<line[i].y2<<endl;
//        }
        Build(1,1,t-1);
//        for(int i=1; i<=t-1; i++){
//            cout<<segTree[i].lf<<" "<<segTree[i].rf<<" "<<segTree[i].cnt<<endl;
//        }
        update(1,line[1], 1, t-1);
//        for(int i=1; i<=t-1; i++){
//            cout<<segTree[i].lf<<" "<<segTree[i].rf<<" "<<segTree[i].cnt<<endl;
//        }
        double res=0;
        for(i=2;i<t;i++)
        {
            //cout<<"int "<<res<<endl;
            res+=node[1].cnt*(line[i].x-line[i-1].x);
            update(1,line[i], 1, t-1);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",iCase,res);
        //看来POJ上%.2f可以过，%.2lf却不行了
    }
    return 0;
}
/*
2
1 1 3 3
1 5 3 7
*/

论文题目

hdu

题目链接
原理可以看吉司机的论文
原理

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
typedef long long ll;
struct Node{
    int dat;
    ll sum;
    int ma, se;
    int t;
    int lazy;
}node[maxn<<2];
int n, q;
int a[maxn];
void push_up(int rt){
    if(node[ls].ma == node[rs].ma){
        node[rt].t = node[ls].t + node[rs].t;
        node[rt].ma = node[ls].ma;
        node[rt].se = max(node[ls].se, node[rs].se);
    }
    else if(node[ls].ma>node[rs].ma){
        node[rt].t = node[ls].t;
        node[rt].ma = node[ls].ma;
        node[rt].se = max(node[ls].se, node[rs].ma);
    }
    else{
        node[rt].t = node[rs].t;
        node[rt].ma = node[rs].ma;
        node[rt].se = max(node[rs].se, node[ls].ma);
    }
    node[rt].sum = node[ls].sum + node[rs].sum;
    return;
}
void build(int rt, int l, int r){
    node[rt].lazy = 0, node[rt].se = -1;
    if(l == r){
        node[rt].ma = a[l];
        node[rt].sum = a[l];
        node[rt].t = 1;
        return;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    push_up(rt);
}
void push_down(int rt){
    int val = node[rt].ma;
    if (node[ls].se< val && node[ls].ma>val) {
        node[ls].sum -= (1ll)*node[ls].t*(node[ls].ma-val);
        node[ls].ma = val;
        node[ls].lazy = 1;
    }
    if (node[rs].se< val && node[rs].ma>val) {
        node[rs].sum -= (1ll)*node[rs].t*(node[rs].ma-val);
        node[rs].ma = val;
        node[rs].lazy = 1;
    }
    node[rt].lazy = 0;
}
void update(int rt, int l, int r, int ql, int qr, int val){
    //cout<<"haha "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    if(ql<=l&&qr>=r){
        //cout<<"in  "<<node[rt].ma<<" "<<node[rt].se<<endl;
        if(val>=node[rt].ma) return ;
        if(val>node[rt].se){
            node[rt].sum -= (1ll)*(node[rt].ma-val)*node[rt].t;
            //cout<<"haha"<<node[rt].sum<<endl;
            node[rt].lazy = 1;
            node[rt].ma = val;
            return;
        }
    }
    if(node[rt].lazy) push_down(rt);
    if(qr<=mid) update(ls, l, mid, ql ,qr, val);
    else if(ql>mid) update(rs, mid+1, r, ql ,qr, val);
    else update(ls, l, mid, ql, qr, val), update(rs, mid+1, r, ql ,qr, val);
    push_up(rt);
}
ll query_mx(int rt, int l ,int r, int ql ,int qr){
    if(ql<=l&&qr>=r){
        return (ll)node[rt].ma;
    }
    if(node[rt].lazy) push_down(rt);
    if(qr <= mid){
        return query_mx(ls, l, mid, ql ,qr);
    }
    else if(ql > mid){
        return query_mx(rs, mid+1, r, ql ,qr);
    }
    else {
        return max(query_mx(ls, l, mid, ql, qr),
                   query_mx(rs, mid+1, r, ql ,qr));
    }
}
ll query_sum(int rt, int l, int r, int ql, int qr){
    if(ql<=l && qr>=r) return node[rt].sum;
    if(node[rt].lazy) push_down(rt);
    if(qr<=mid) return query_sum(ls, l, mid, ql ,qr);
    else if(ql>mid) return query_sum(rs, mid+1, r, ql ,qr);
    else return query_sum(ls, l, mid, ql ,qr)+
                query_sum(rs, mid+1, r, ql ,qr);
}
int main(){
    ios::sync_with_stdio(false);
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &q);
        for(int i=1; i<=n; i++){
            scanf("%d", &a[i]);
        }
        build(1, 1, n);
        int op, l, r, val;
        for(int i=1; i<=q; i++){
            scanf("%d", &op);
            if(op == 0){
                scanf("%d%d%d", &l, &r, &val);
                update(1, 1, n, l, r, val);
//                for(int i=1; i<=12; i++){
//                    cout<<i<<" "<<node[i].ma<<" "<<node[i].se<<" "<<node[i].sum<<endl;
//                }
            }
            else if(op == 1){
                scanf("%d%d", &l, &r);
                printf("%lld\n", query_mx(1, 1, n, l, r));
            }
            else{
                scanf("%d%d", &l,&r);
                printf("%lld\n", query_sum(1, 1, n, l, r));
            }
        }
    }
    return 0;
}
/*
1
5 5
1 2 3 4 5
0 3 5 3
1 1 5
*/

论文的例二

最假女选手

只有阉割版本的功能

增加了一个懒标记，注意两个懒标记之间的优先级的关系，lazy1的优先级大于lazy,当要更新lazy1标记的时候，要先将lazy标记pushdown.

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
typedef long long ll;
struct Node{
    ll sum;
    int ma, se;
    int t;
    int lazy;
    int lazy1;
}node[maxn<<2];
int n, q;
int a[maxn];
 
void push_up(int rt){
    if(node[ls].ma == node[rs].ma){
        node[rt].t = node[ls].t + node[rs].t;
        node[rt].ma = node[ls].ma;
        node[rt].se = max(node[ls].se, node[rs].se);
    }
    else if(node[ls].ma>node[rs].ma){
        node[rt].t = node[ls].t;
        node[rt].ma = node[ls].ma;
        node[rt].se = max(node[ls].se, node[rs].ma);
    }
    else{
        node[rt].t = node[rs].t;
        node[rt].ma = node[rs].ma;
        node[rt].se = max(node[rs].se, node[ls].ma);
    }
    node[rt].sum = node[ls].sum + node[rs].sum;
    return;
}
 
void build(int rt, int l, int r){
    node[rt].lazy = node[rt].lazy1 = 0, node[rt].se = -1e9;
    if(l == r){
        node[rt].ma = a[l];
        node[rt].sum = a[l];
        node[rt].t = 1;
        return;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    push_up(rt);
}
 
void push_down(int rt, int l, int r){
    if(!(l < r)) return ;
    int val = node[rt].ma;
    int len1 = (mid-l+1);
    int len2 = r-mid;
    if(node[rt].lazy1){
        node[ls].sum += (node[rt].lazy1)*len1;
        node[rs].sum += node[rt].lazy1*len2;
        node[ls].se += node[rt].lazy1;
        node[rs].se += node[rt].lazy1;
        node[ls].ma += node[rt].lazy1;
        node[rs].ma += node[rt].lazy1;
        node[ls].lazy1 += node[rt].lazy1;
        node[rs].lazy1 += node[rt].lazy1;
    }
    if (node[rt].lazy&&node[ls].se< val && node[ls].ma>val) {
        node[ls].sum -= (1ll)*node[ls].t*(node[ls].ma-val);
        node[ls].ma = val;
        node[ls].lazy = 1;
        //node[ls].lazy1 = 0;
    }
    if (node[rt].lazy&&node[rs].se< val && node[rs].ma>val) {
        node[rs].sum -= (1ll)*node[rs].t*(node[rs].ma-val);
        node[rs].ma = val;
        node[rs].lazy = 1;
        //node[rt].lazy1 = 0;
    }
    node[rt].lazy1 = 0;
    node[rt].lazy = 0;
}
 
void update(int rt, int l, int r, int ql, int qr, int val){
    //cout<<"haha "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    if(ql<=l&&qr>=r){
        //cout<<"in  "<<node[rt].ma<<" "<<node[rt].se<<endl;
        if(node[rt].lazy1) push_down(rt, l, r);
        if(val>=node[rt].ma) return ;
        if(val>node[rt].se){
            node[rt].sum -= (1ll)*(node[rt].ma-val)*node[rt].t;
            //cout<<"haha"<<node[rt].sum<<endl;
            node[rt].lazy = 1;
            node[rt].ma = val;
            return;
        }
    }
    if(node[rt].lazy||node[rt].lazy1) push_down(rt, l, r);
    if(qr<=mid) update(ls, l, mid, ql ,qr, val);
    else if(ql>mid) update(rs, mid+1, r, ql ,qr, val);
    else update(ls, l, mid, ql, qr, val), update(rs, mid+1, r, ql ,qr, val);
    push_up(rt);
}
 
ll query_mx(int rt, int l ,int r, int ql ,int qr){
    if(ql<=l&&qr>=r){
        return (ll)node[rt].ma;
    }
    if(node[rt].lazy||node[rt].lazy1) push_down(rt, l, r);
    ll ans;
    if(qr <= mid){
        ans = query_mx(ls, l, mid, ql ,qr);
    }
    else if(ql > mid){
        ans = query_mx(rs, mid+1, r, ql ,qr);
    }
    else {
        ans = max(query_mx(ls, l, mid, ql, qr),
                   query_mx(rs, mid+1, r, ql ,qr));
    }
    push_up(rt);
    return ans;
}
 
 
ll query_sum(int rt, int l, int r, int ql, int qr){
    if(ql<=l && qr>=r) return node[rt].sum;
    if(node[rt].lazy||node[rt].lazy1) push_down(rt, l, r);
    if(qr<=mid) return query_sum(ls, l, mid, ql ,qr);
    else if(ql>mid) return query_sum(rs, mid+1, r, ql ,qr);
    else return query_sum(ls, l, mid, ql ,qr)+
                query_sum(rs, mid+1, r, ql ,qr);
}
 
void add(int rt, int l, int r, int ql, int qr, int val){
    if(ql<=l&&qr>=r){
//        if(node[rt].lazy){
//            push_down(rt, l, r);
//        }
        node[rt].lazy1 += val;
        node[rt].ma += val;
        node[rt].sum += (r-l+1)*val;
        node[rt].se += val;
        return;
    }
    if(node[rt].lazy||node[rt].lazy1) push_down(rt, l, r);
    if(qr<=mid) add(ls, l, mid, ql ,qr, val);
    else if(ql>mid) add(rs, mid+1, r, ql ,qr, val);
    else add(ls, l, mid, ql ,qr, val), add(rs, mid+1, r, ql, qr, val);
    push_up(rt);
}
 
 
int main(){
    //ios::sync_with_stdio(false);
    //freopen("3.in", "r", stdin);
    scanf("%d", &n);
    assert(1 <= n && n <= 100000);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    int op, l, r, val;
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%d%d", &l, &r, &val);
            assert(l <= r && 1 <= l && l <= n && 1 <= r && r <= n);
            update(1, 1, n, l, r, val);
//                for(int i=1; i<=12; i++){
//                    cout<<i<<" "<<node[i].ma<<" "<<node[i].se<<" "<<node[i].sum<<endl;
//                }
        }
//            else if(op == 1){
//                scanf("%d%d", &l, &r);
//                printf("%lld\n", query_mx(1, 1, n, l, r));
//            }
        else if(op == 3){
            scanf("%d%d", &l,&r);
            assert(l <= r && 1 <= l && l <= n && 1 <= r && r <= n);
            printf("%lld\n", query_sum(1, 1, n, l, r));
        }
        else {
            scanf("%d%d%d", &l, &r, &val);
            assert(l <= r && 1 <= l && l <= n && 1 <= r && r <= n);
            add(1, 1, n, l, r, val);
        }
    }
    return 0;
}
/*
1
2 2
1 2
1 1 2 1
3 1 2
*/

uoj169

这类更新不能使用懒标记进行相应的更新
同类型的题目：
bzoj 3064 题解
bzoj 4355
圣诞老人和序列
由于这道题过的人比较的少，感觉教程比较的少，下面的这个教程他有一组数据是T的，但是感觉他讲更仔细一些
原理

ac code

uoj170

Picks loves segment tree VIII

偷一波板子

支持的操作：

  1. 对于所有的 i∈[l,r]i∈[l,r]，将 \(A_i 变成 A_i+c\)。
  2. 对于所有的 i∈[l,r]i∈[l,r]，将 \(A_i 变成 max(A_i,d)\)。
  3. 对于所有的 i∈[l,r]i∈[l,r]，询问 \(A_i\) 的最小值。
  4. 对于所有的 i∈[l,r]i∈[l,r]，询问 \(B_i\) 的最小值。
  5. 对于所有的 i∈[l,r]i∈[l,r]，将 \(A_i\) 变成 \(min(A_i,e)\)。
  6. 对于所有的 i∈[l,r]i∈[l,r]，询问 \(C_i\) 的最大值。

进行一次更新：对于所有的 i∈[1,n]i∈[1,n]，将 \(B_i 变成 min(B_i,A_i)，C_i 变成 max(C_i,A_i)\)。
感觉这道题就是uoj169的加强版
B, C数组就是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
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
#include <cctype>
#include <cstdio>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define mid ((l+r)>>1)
#define lc tr[t<<1]
#define rc tr[t<<1|1]
#define lson l,mid,t<<1
#define rson mid+1,r,t<<1|1
using namespace std;
typedef long long ll;
int get()
{
    static char pool[1<<22],*tpr=pool+(1<<22),*tp=tpr;
    #define getchar() (tp<tpr? 0:fread(tp=pool,1,1<<22,stdin),*tp++)
    char c;
    while (!isdigit(c=getchar()) && c!='-');
    int s=c=='-'? -1:1,k=~s? c-'0':0;
    for (; isdigit(c=getchar()); k=k*10+c-'0');
    return s*k;
}
const int inf=0x7fffffff,cinf=0x3f3f3f3f;
int n,m,op,ql,qr,c,hmx,hmn,mn;
struct lazy
{
    int c,mn,mx;
    lazy():c(),mn(cinf),mx(-cinf){}
    lazy(int k):c(k),mn(k),mx(k){}
    void operator+=(const lazy &x)
    {
        mn=min(mn,c+x.mn),mx=max(mx,c+x.mx),c+=x.c;
    }
};
struct node
{
    int mn0,mn,hmn,mx0,mx,hmx,mnp,mxp;
    lazy mnc,mxc,tag;
    node(){}
    node(int k):mn0(k),mn(k),hmn(k),mx0(k),mx(k),hmx(k),mnp(inf),mxp(-inf),mnc(),mxc(),tag(){}
    void incmn(const lazy &c)
    {
        mxp==mn? mxp=mn+c.c:0,hmn=min(hmn,mn+c.mn),mnc+=c,mn+=c.c;
    }
    void incmx(const lazy &c)
    {
        mnp==mx? mnp=mx+c.c:0,hmx=max(hmx,mx+c.mx),mxc+=c,mx+=c.c;
    }
    void inc(const lazy &c)
    {
        mnp>mxp? 0:(tag+=c,mnp+=c.c,mxp+=c.c);
    }
    void incr(int c)
    {
        incmn(c),incmx(c),inc(c);
    }
    void maxi(int c)
    {
        incmn(c-=mn),mn0<mx0? void():incmx(c);
    }
    void mini(int c)
    {
        incmx(c-=mx),mn0<mx0? void():incmn(c);
    }
    void modify(const node &c)
    {
        incmn(mn==c.mn0? c.mnc:mn==c.mx0? c.mxc:c.tag);
        incmx(mx==c.mx0? c.mxc:mx==c.mn0? c.mnc:c.tag);
        inc(c.tag);
    }
    void pushdown(node &l,node &r)
    {
        l.modify(*this),r.modify(*this),mnc=mxc=tag=lazy(),mn0=mn,mx0=mx;
    }
    void pushup(const node &l,const node &r)
    {
        hmn=min(l.hmn,r.hmn),mn0=mn=min(l.mn,r.mn),mnp=min(mn<l.mn? l.mn:l.mnp,mn<r.mn? r.mn:r.mnp);
        hmx=max(l.hmx,r.hmx),mx0=mx=max(l.mx,r.mx),mxp=max(mx>l.mx? l.mx:l.mxp,mx>r.mx? r.mx:r.mxp);
    }
} tr[1<<20|1];
void build(int l=1,int r=n,int t=1)
{
    if (l==r)
        return void(tr[t]=get());
    build(lson),build(rson);
    tr[t].pushup(lc,rc);
}
void incr(int l=1,int r=n,int t=1)
{
    if (ql<=l && r<=qr)
        return tr[t].incr(c);
    tr[t].pushdown(lc,rc);
    if (ql<=mid)
        incr(lson);
    if (mid<qr)
        incr(rson);
    tr[t].pushup(lc,rc);
}
void maxi(int l=1,int r=n,int t=1)
{
    if (c<=tr[t].mn)
        return;
    if (ql<=l && r<=qr && c<tr[t].mnp)
        return tr[t].maxi(c);
    tr[t].pushdown(lc,rc);
    if (ql<=mid)
        maxi(lson);
    if (mid<qr)
        maxi(rson);
    tr[t].pushup(lc,rc);
}
void mini(int l=1,int r=n,int t=1)
{
    if (c>=tr[t].mx)
        return;
    if (ql<=l && r<=qr && c>tr[t].mxp)
        return tr[t].mini(c);
    tr[t].pushdown(lc,rc);
    if (ql<=mid)
        mini(lson);
    if (mid<qr)
        mini(rson);
    tr[t].pushup(lc,rc);
}
void query(int l=1,int r=n,int t=1)
{
    if (ql<=l && r<=qr)
        return hmx=max(hmx,tr[t].hmx),mn=min(mn,tr[t].mn),hmn=min(hmn,tr[t].hmn),void();
    tr[t].pushdown(lc,rc);
    if (ql<=mid)
        query(lson);
    if (mid<qr)
        query(rson);
}
int main()
{
    n=get(),m=get();
    build();
    while (m--)
        if (op=get(),ql=get(),qr=get(),op==3 || op==4 || op==6)
            hmn=mn=inf,hmx=-inf,query(),printf("%d\n",op==3? mn:op==4? hmn:hmx);
        else
            c=get(),op==1? incr():op==2? maxi():mini();
    return 0;
}

未解决的问题

本文标题:暑假补遗

文章作者:Babydragon

发布时间:2018-08-04, 23:43:01

最后更新:2018-08-09, 20:12:08

原始链接:http://baolintian.github.io/2018/08/04/暑假补遗/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 并查集
    1. 1.1. 关押罪犯
      1. 1.1.1. ac code
    2. 1.2. poj移动木块
      1. 1.2.1. ac code
  2. 2. 网络流
    1. 2.1. miking way
      1. 2.1.1. ac code
  3. 3. 线段树
    1. 3.1. 单点更新，区间查询
    2. 3.2. 区间更新，区间、单点查询
    3. 3.3. 扫描线
    4. 3.4. 论文题目
      1. 3.4.1. hdu
      2. 3.4.2. ac code
      3. 3.4.3. 论文的例二
        1. 3.4.3.1. 只有阉割版本的功能
        2. 3.4.3.2. ac code
      4. 3.4.4. uoj169
        1. 3.4.4.1. ac code
      5. 3.4.5. uoj170
        1. 3.4.5.1. 偷一波板子
        2. 3.4.5.2. 别人的代码
  4. 4. 未解决的问题
{{ live2d() }}