1. 区间翻转 (洛谷 p3391)
- #include <set>
- #include <map>
- #include <deque>
- #include <queue>
- #include <stack>
- #include <cmath>
- #include <ctime>
- #include <bitset>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- typedef long long ll;
- typedef pair<LL, LL> pLL;
- typedef pair<LL, int> pLi;
- typedef pair<int, LL> pil;;
- typedef pair<int, int> pii;
- typedef unsigned long long uLL;
- #define ls rt<<1
- #define rs rt<<1|1
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define bug printf("*********\n")
- #define FIN freopen("input.txt","r",stdin);
- #define FON freopen("output.txt","w+",stdout);
- #define IO iOS::sync_with_stdio(false),cin.tie(0)
- #define debug1(x) cout<<"["<<#x<<""<<(x)<<"]\n"#define debug2(x, y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x, y, z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
- const double eps = 1e-8;
- const int mod = 1e9 + 7;
- const int maxn = 3e5 + 5;
- const int INF = 0x3f3f3f3f;
- const LL INFLL = 0x3f3f3f3f3f3f3f3f;
- const int N = 100005;
- int ch[N][2], par[N], val[N], cnt[N], size[N], rev[N], root, ncnt;
- int n, m, x, y;
- bool chk(int x) {
- return ch[par[x]][1] == x;
- }
- void pushup(int x) {
- size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
- }
- void pushdown(int x) {
- if (rev[x]) {
- swap(ch[x][0], ch[x][1]);
- rev[ch[x][0]] ^= 1;
- rev[ch[x][1]] ^= 1;
- rev[x] = 0;
- }
- }
- void rotate(int x) {
- int y = par[x], z = par[y], k = chk(x), w = ch[x][k ^ 1];
- ch[y][k] = w; par[w] = y;
- ch[z][chk(y)] = x; par[x] = z;
- ch[x][k ^ 1] = y; par[y] = x;
- pushup(y); pushup(x);
- }
- void splay(int x, int goal = 0) {
- while (par[x] != goal) {
- int y = par[x], z = par[y];
- if (z != goal) {
- if (chk(x) == chk(y)) rotate(y);
- else rotate(x);
- }
- rotate(x);
- }
- if (!goal) root = x;
- }
- void insert(int x) {
- int cur = root, p = 0;
- while (cur && val[cur] != x) {
- p = cur;
- cur = ch[cur][x> val[cur]];
- }
- if (cur) {
- cnt[cur]++;
- } else {
- cur = ++ncnt;
- if (p) ch[p][x> val[p]] = cur;
- ch[cur][0] = ch[cur][1] = 0;
- par[cur] = p; val[cur] = x;
- cnt[cur] = size[cur] = 1;
- }
- splay(cur);
- }
- void find(int x) {
- int cur = root;
- while (ch[cur][x> val[cur]] && val[cur] != x) {
- cur = ch[cur][x> val[cur]];
- }
- splay(cur);
- }
- int kth(int k) {
- int cur = root;
- while (1) {
- pushdown(cur);
- if (ch[cur][0] && k <= size[ch[cur][0]]) {
- cur = ch[cur][0];
- } else if (k> size[ch[cur][0]] + cnt[cur]) {
- k -= size[ch[cur][0]] + cnt[cur];
- cur = ch[cur][1];
- } else {
- return cur;
- }
- }
- }
- void reverse(int l, int r) {
- int x = kth(l), y = kth(r + 2);
- splay(x); splay(y, x);
- rev[ch[y][0]] ^= 1;
- }
- int pre(int x) {
- find(x);
- if (val[root] <x) return root;
- int cur = ch[root][0];
- while (ch[cur][1]) cur = ch[cur][1];
- return cur;
- }
- int succ(int x) {
- find(x);
- if (val[root]> x) return root;
- int cur = ch[root][1];
- while (ch[cur][0]) cur = ch[cur][0];
- return cur;
- }
- void output(int x) {
- pushdown(x);
- if (ch[x][0]) output(ch[x][0]);
- if (val[x] && val[x] <= n) printf("%d", val[x]);
- if (ch[x][1]) output(ch[x][1]);
- }
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 0; i <= n + 1; i++) insert(i);
- while (m--) {
- scanf("%d%d", &x, &y);
- reverse(x, y);
- }
- output(root);
- }
2. 区间插入, 删除, 修改, 翻转, 求和, 最最大子列 (洛谷 P2042)
- #include <set>
- #include <map>
- #include <deque>
- #include <queue>
- #include <stack>
- #include <cmath>
- #include <ctime>
- #include <bitset>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- typedef long long ll;
- typedef pair<LL, LL> pLL;
- typedef pair<LL, int> pLi;
- typedef pair<int, LL> pil;;
- typedef pair<int, int> pii;
- typedef unsigned long long uLL;
- #define ls rt<<1
- #define rs rt<<1|1
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define bug printf("*********\n")
- #define FIN freopen("input.txt","r",stdin);
- #define FON freopen("output.txt","w+",stdout);
- #define IO iOS::sync_with_stdio(false),cin.tie(0)
- #define debug1(x) cout<<"["<<#x<<""<<(x)<<"]\n"#define debug2(x, y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x, y, z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
- const double eps = 1e-8;
- const int mod = 1e9 + 7;
- const int maxn = 3e5 + 5;
- const int INF = 0x3f3f3f3f;
- const LL INFLL = 0x3f3f3f3f3f3f3f3f;
- const int N = 1000016;
- int size[N], sum[N], upd[N], rev[N], la[N], ra[N], gss[N];
- int val[N], ch[N][2], par[N], ncnt, root;
- queue<int> q;
- void recycle(int x) {
- if (ch[x][0]) recycle(ch[x][0]);
- if (ch[x][1]) recycle(ch[x][1]);
- q.push(x);
- }
- inline int newNode(int x) {
- int cur;
- if (q.empty()) cur = ++ncnt;
- else cur = q.front(), q.pop();
- ch[cur][0] = ch[cur][1] = par[cur] = 0;
- val[cur] = sum[cur] = gss[cur] = x;
- la[cur] = ra[cur] = max(0, x);
- upd[cur] = rev[cur] = 0;
- size[cur] = 1;
- return cur;
- }
- inline bool chk(int x) {
- return ch[par[x]][1] == x;
- }
- inline void pushup(int x) {
- int l = ch[x][0], r = ch[x][1];
- size[x] = size[l] + size[r] + 1;
- sum[x] = sum[l] + sum[r] + val[x];
- // 这里和线段树不同, 线段树只有叶子上有权值, 平衡树上所有点都有, 必须 + val[x]
- la[x] = max(la[l], sum[l] + val[x] + la[r]);
- ra[x] = max(ra[r], sum[r] + val[x] + ra[l]);
- gss[x] = max(ra[l] + val[x] + la[r], max(gss[l], gss[r]));
- }
- inline void rotate(int x) {
- int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
- ch[y][k] = w; par[w] = y;
- ch[z][chk(y)] = x; par[x] = z;
- ch[x][k^1] = y; par[y] = x;
- pushup(y); pushup(x);
- }
- inline void pushdown(int x) {
- int l = ch[x][0], r = ch[x][1];
- if (upd[x]) {
- upd[x] = rev[x] = 0;
- if (l) {
- upd[l] = 1; val[l] = val[x];
- sum[l] = val[x] * size[l];
- la[l] = ra[l] = max(sum[l], 0);
- gss[l] = val[x] <0 ? val[x] : sum[l];
- }
- if (r) {
- upd[r] = 1; val[r] = val[x];
- sum[r] = val[x] * size[r];
- la[r] = ra[r] = max(sum[r], 0);
- gss[r] = val[x] < 0 ? val[x] : sum[r];
- }
- }
- if (rev[x]) {
- rev[l] ^= 1; rev[r] ^= 1; rev[x] = 0;
- swap(la[l], ra[l]); swap(la[r], ra[r]);
- swap(ch[l][0], ch[l][1]);
- swap(ch[r][0], ch[r][1]);
- }
- }
- inline void splay(int x, int goal = 0) {
- while (par[x] != goal) {
- int y = par[x], z = par[y];
- if (z != goal) {
- if (chk(x) == chk(y)) rotate(y);
- else rotate(x);
- }
- rotate(x);
- }
- if (!goal) root = x;
- }
- int build(int l, int r, int *arr) {
- if (l> r) return 0;
- int mid = (l+r)>>1, cur = newNode(arr[mid]);
- if (l == r) return cur;
- if ((ch[cur][0] = build(l, mid-1, arr))) par[ch[cur][0]] = cur;
- if ((ch[cur][1] = build(mid+1, r, arr))) par[ch[cur][1]] = cur;
- pushup(cur);
- return cur;
- }
- inline int kth(int k) {
- int cur = root;
- while (1) {
- pushdown(cur);
- if (ch[cur][0] && k <= size[ch[cur][0]]) {
- cur = ch[cur][0];
- } else if (k> size[ch[cur][0]] + 1) {
- k -= size[ch[cur][0]] + 1;
- cur = ch[cur][1];
- } else {
- return cur;
- }
- }
- }
- inline void insert(int x, int y) {
- int u = kth(x+1), v = kth(x+2);
- splay(u); splay(v, u);
- ch[v][0] = y; par[y] = v;
- pushup(v); pushup(u);
- }
- inline int qsum(int x, int y) {
- int u = kth(x), v = kth(x+y+1);
- splay(u); splay(v, u);
- return sum[ch[v][0]];
- }
- inline int qgss() {
- return gss[root];
- }
- inline void remove(int x, int y) {
- int u = kth(x), v = kth(x+y+1);
- splay(u); splay(v, u);
- recycle(ch[v][0]);
- ch[v][0] = 0;
- pushup(v); pushup(u);
- }
- inline void reverse(int x, int y) {
- int u = kth(x), v = kth(x+y+1);
- splay(u); splay(v, u);
- int w = ch[v][0];
- if (!upd[w]) {
- rev[w] ^= 1;
- swap(ch[w][0], ch[w][1]);
- swap(la[w], ra[w]);
- pushup(v); pushup(u);
- }
- }
- inline void update(int x, int y, int z) {
- int u = kth(x), v = kth(x+y+1);
- splay(u); splay(v, u);
- int w = ch[v][0];
- upd[w] = 1; val[w] = z; sum[w] = size[w] * z;
- la[w] = ra[w] = max(0, sum[w]);
- gss[w] = z < 0 ? z : sum[w];
- pushup(v); pushup(u);
- }
- int n, m, arr[N], c, x, y, z;
- char buf[32];
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 2; i <= n+1; i++) {
- scanf("%d", arr+i);
- }
- gss[0] = val[0] = 0xcfcfcfcf;
- arr[1] = arr[n += 2] = 0xcfcfcfcf;
- build(1, n, arr); root = 1;
- while (m--) {
- scanf("%s", buf);
- switch ((buf[2] + buf[1]) ^ *buf) {
- case 'G'^('E'+'T'):
- scanf("%d%d", &x, &y);
- printf("%d\n", qsum(x, y));
- break;
- case 'M'^('A'+'X'):
- printf("%d\n", qgss());
- break;
- case 'R'^('E'+'V'):
- scanf("%d%d", &x, &y);
- reverse(x, y);
- break;
- case 'M'^('A'+'K'):
- scanf("%d%d%d", &x, &y, &z);
- update(x, y, z);
- break;
- case 'D'^('E'+'L'):
- scanf("%d%d", &x, &y);
- remove(x, y);
- break;
- case 'I'^('N'+'S'):
- scanf("%d%d", &x, &y);
- memset(arr, 0, sizeof arr);
- for (int i = 1; i <= y; i++) {
- scanf("%d", arr+i);
- }
- insert(x, build(1, y, arr));
- break;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3119094.html