任重而道远

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int N = 1e5 + 5; struct Node { ll val, maxn; Node *ls, *rs; void update (void) { val = ls -> val + rs -> val; maxn = max (ls -> maxn, rs -> maxn); } }pool[N << 1], *tail = pool, *root, *zero; ll n, m; ll a[N]; ll read () { ll x = 0, jud = 1; char c = getchar (); while (c < '0' || c > '9') {if (c == '-') jud = -1; c = getchar ();} while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar ();} return x * jud; } void init () { zero = ++tail; zero -> ls = zero -> rs = zero; zero -> val = zero -> maxn = 0; } Node *newnode () { Node *nd = ++tail; nd -> ls = nd -> rs = zero; nd -> val = nd -> maxn = 0; return nd; } Node *build (ll l, ll r) { Node *nd = newnode (); if (l == r) { nd -> val = a[l]; nd -> maxn = a[l]; } else { int mid = l + r >> 1; nd -> ls = build (l, mid); nd -> rs = build (mid + 1, r); nd -> update (); } return nd; } void modify (Node *nd, ll l, ll r, ll o, ll val) { if (l == r) { nd -> val = val; nd -> maxn = val; } else { int mid = l + r >> 1; if (o <= mid) modify (nd -> ls, l, mid, o, val); else modify (nd -> rs, mid + 1, r, o, val); nd -> update (); } } void modify (Node *nd, ll l, ll r, ll L, ll R, ll Mod) { if (nd -> maxn < Mod) return; if (l == r) { nd -> val %= Mod; nd -> maxn = nd -> val; } else { int mid = l + r >> 1; if (L <= mid) modify (nd -> ls, l, mid, L, R, Mod); if (R > mid) modify (nd -> rs, mid + 1, r, L, R, Mod); nd -> update (); } } ll query (Node *nd, ll l, ll r, ll L, ll R) { if (L <= l && R >= r) return nd -> val; int mid = l + r >> 1; ll rt = 0; if (L <= mid) rt += query (nd -> ls, l, mid, L, R); if (mid < R) rt += query (nd -> rs, mid + 1, r, L, R); return rt; } int main () { freopen ("mod.in", "r", stdin); freopen ("mod.out", "w", stdout); n = read (), m = read (), init (); for (int i = 1; i <= n; i++) a[i] = read (); root = build (1, n); while (m--) { ll opt = read (); if (opt == 1) { ll l = read (), r = read (); printf ("%lld\n", query (root, 1, n, l, r)); } else if (opt == 2) { ll l = read (), r = read (), x = read (); modify (root, 1, n, l, r, x); } else { ll k = read (), y = read (); modify (root, 1, n, k, y); } } return 0; }

描述

给一个长为N的数列，有M次操作，每次操作时以下三种之一：

（1）修改数列中的一个数

（2）求数列中某连续一段所有数的两两乘积的和 mod 1000000007

（3）求数列中某连续一段所有相邻两数乘积的和 mod 1000000007

输入

第一行两个正整数N和M。 第二行N的整数表示这个数列。 接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来两个整数x和y，表示把x位置的值修改为y；若该字符为'Q'，则表示一个询问操作，接下来两个整数x和y，表示对[x,y]区间做2号询问；若该字符为'A'，则表示一个询问操作，接下来两个整数x和y，表示对[x,y]区间做3号询问。

输出

对每一个询问操作单独输出一行，表示答案。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int N = 1e5 + 5, Mod = 1e9 + 7; struct Node { ll val, sum, tot, lf, rg; Node *ls, *rs; void update (void) { sum = (ls -> sum + rs -> sum) % Mod; tot = (ls -> sum * rs -> sum % Mod + ls -> tot + rs -> tot) % Mod; lf = ls -> lf, rg = rs -> rg; val = ((ls -> val + rs -> val + ls -> rg * rs -> lf % Mod) % Mod + Mod) % Mod; } }pool[N << 1], *tail = pool, *root, *zero; struct Point {ll sum, tot;}; ll n, m, x, y; ll a[N]; void init () { zero = ++tail; zero -> ls = zero -> rs = zero; zero -> val = zero -> sum = zero -> lf = zero -> rg = 0; } Node *newnode () { Node *nd = ++tail; nd -> ls = nd -> rs = zero; nd -> val = nd -> sum = nd -> lf = nd -> rg = 0; return nd; } Node *build (int l, int r) { Node *nd = newnode (); if (l == r) { nd -> val = 0; nd -> sum = nd -> lf = nd -> rg = (a[l] % Mod + Mod) % Mod; } else { int mid = l + r >> 1; nd -> ls = build (l, mid); nd -> rs = build (mid + 1, r); nd -> update (); } return nd; } void modify (Node *nd, int l, int r, int o, int val) { if (l == r) { nd -> sum = nd -> lf = nd -> rg = (val % Mod + Mod) % Mod; } else { int mid = l + r >> 1; if (o <= mid) modify (nd -> ls, l, mid, o, val); else modify (nd -> rs, mid + 1, r, o, val); nd -> update (); } } Point query_1 (Node *nd, int l, int r, int L, int R) { if (L <= l && R >= r) return (Point) {nd -> sum, nd -> tot}; int mid = l + r >> 1, ok1 = 0, ok2 = 0; Point p1, p2; if (L <= mid) { p1 = query_1 (nd -> ls, l, mid, L, R); ok1 = 1; } if (R > mid) { p2 = query_1 (nd -> rs, mid + 1, r, L, R); ok2 = 1; } if (ok1 && ok2) return (Point) {((p1.sum + p2.sum) % Mod + Mod) % Mod, ((p1.sum * p2.sum % Mod + p1.tot + p2.tot) % Mod + Mod) % Mod}; else if (ok1) return p1; else return p2; } ll query_2 (Node *nd, int l, int r, int L, int R) { if (L <= l && R >= r) return nd -> val; int mid = l + r >> 1, ok1 = 0, ok2 = 0; ll sww = 0; if (L <= mid) { sww = ((sww + query_2 (nd -> ls, l, mid, L, R)) % Mod + Mod) % Mod; ok1 = 1; } if (R > mid) { sww = ((sww + query_2 (nd -> rs, mid + 1, r, L, R)) % Mod + Mod) % Mod; ok2 = 1; } if (ok1 && ok2) sww = ((sww + nd -> ls -> rg * nd -> rs -> lf) % Mod + Mod) % Mod; return sww; } int main () { init (); scanf ("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]); root = build (1, n); while (m--) { char opt = getchar(); while (opt != 'Q' && opt != 'A' && opt != 'M') opt = getchar(); scanf ("%lld%lld", &x, &y); if (opt == 'M') { modify (root, 1, n, x, y); } else if (opt == 'Q') { printf ("%lld\n", query_1 (root, 1, n, x, y).tot); } else { printf ("%lld\n", query_2 (root, 1, n, x, y)); } } return 0; }

描述

给一个长为N的数列，有M次操作，每次操作是以下两种之一：

（1）修改数列中的一个数

（2）求数列中某位置在某次操作后的值

输入

第一行两个正整数N和M。 第二行N个整数表示这个数列。 接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来两个整数x和y，表示把x位置的值修改为y；若该字符为'Q'，则表示一个询问操作，接下来两个整数x和y，表示求x位置在第y次操作后的值。

输出

对每一个询问操作单独输出一行，表示答案。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e5 + 5; struct Node { int val; Node *ls, *rs; }pool[N * 20], *tail = pool, *root[N]; int n, m, x, y, a[N]; char opt[10]; Node *build (int l, int r) { Node *nd = ++tail; if (l == r) { nd -> val = a[l]; } else { int mid = l + r >> 1; nd -> ls = build (l, mid); nd -> rs = build (mid + 1, r); } return nd; } Node *modify (Node *rt, int l, int r, int o, int val) { Node *nd = ++tail; if (l == r) { nd -> val = val; } else { int mid = l + r >> 1; if (o <= mid) { nd -> ls = modify (rt -> ls, l, mid, o, val); nd -> rs = rt -> rs; } else { nd -> ls = rt -> ls; nd -> rs = modify (rt -> rs, mid + 1, r, o, val); } } return nd; } int query (Node *nd, int l, int r, int o) { if (l == r) return nd -> val; int mid = l + r >> 1; if (o <= mid) return query (nd -> ls, l, mid, o); else return query (nd -> rs, mid + 1, r, o); } int main () { scanf ("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf ("%d", &a[i]); root[0] = build (1, n); for (int i = 1; i <= m; i++) { scanf ("%s", opt); scanf ("%d%d", &x, &y); if (opt[0] == 'M') { root[i] = modify (root[i - 1], 1, n, x, y); } else { printf ("%d\n", query (root[y], 1, n, x)); root[i] = root[i - 1]; } } return 0; }

描述

给一个空数列，有M次操作，每次操作是以下三种之一：

（1）在数列后加一个数

（2）求数列中某位置的值

（3）撤销掉最后进行的若干次操作（1和3）

输入

第一行一个正整数M。 接下来M行，每行开头是一个字符，若该字符为'A'，则表示一个加数操作，接下来一个整数x，表示在数列后加一个整数x；若该字符为'Q'，则表示一个询问操作，接下来一个整数x，表示求x位置的值；若该字符为'U'，则表示一个撤销操作，接下来一个整数x，表示撤销掉最后进行的若干次操作。

输出

对每一个询问操作单独输出一行，表示答案。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e5 + 5; struct Node { int val; Node *ls, *rs; }pool[N * 20], *tail = pool, *root[N], *zero; int m, x, tot, siz[N]; char opt[10]; Node *newnode () { Node *nd = ++tail; nd -> ls = nd -> rs = zero; nd -> val = 0; return nd; } void init () { zero = ++tail; zero -> ls = zero -> rs = zero; zero -> val = 0; root[0] = newnode (); } Node *modify (Node *rt, int l, int r, int o, int val) { Node *nd = newnode (); if (l == r) { nd -> val = val; } else { int mid = l + r >> 1; if (o <= mid) { nd -> ls = modify (rt -> ls, l, mid, o, val); nd -> rs = rt -> rs; } else { nd -> ls = rt -> ls; nd -> rs = modify (rt -> rs, mid + 1, r, o, val); } } return nd; } int query (Node *nd, int l, int r, int o) { if (l == r) return nd -> val; int mid = l + r >> 1; if (o <= mid) return query (nd -> ls, l, mid, o); else return query (nd -> rs, mid + 1, r, o); } int main () { scanf ("%d", &m); init (); while (m--) { scanf ("%s", opt); scanf ("%d", &x); if (opt[0] == 'A') { tot++; siz[tot] = siz[tot - 1] + 1; root[tot] = modify (root[tot - 1], 1, N, siz[tot], x); } else if (opt[0] == 'Q') { printf ("%d\n", query (root[tot], 1, N, x)); } else { tot++; siz[tot] = siz[tot - x - 1]; root[tot] = root[tot - x - 1]; } } return 0; }

描述

给一个长为N的数列，有M次操作，每次操作是以下两种之一：

（1）将某连续一段同时改成一个数

（2）求数列中某连续一段的和

输入

第一行两个正整数N和M。 第二行N的整数表示这个数列。 接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来三个整数x、y和z，表示在[x,y]这段区间的数改为z；若该字符为'Q'，则表示一个询问操作，接下来两个整数x和y，表示求[x,y]这段区间的和。

输出

对每一个询问操作单独输出一行，表示答案。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int N = 1e5 + 5; struct Node { ll val, tag, flag; Node *ls, *rs; void update (void) { val = ls -> val + rs -> val; } }pool[N << 1], *tail = pool, *root, *zero; ll n, m, a[N]; ll read () { ll x = 0, f = 1; char c = getchar (); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar ();} while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar ();} return x * f; } void init () { zero = ++tail; zero -> ls = zero -> rs = zero; zero -> val = zero -> tag = zero -> flag = 0; } Node *newnode () { Node *nd = ++tail; nd -> ls = nd -> rs = zero; nd -> val = nd -> tag = nd -> flag = 0; return nd; } void push_down (Node *nd, ll l, ll r) { if (nd -> flag) { int mid = l + r >> 1; nd -> ls -> val = nd -> tag * (mid - l + 1); nd -> rs -> val = nd -> tag * (r - mid); nd -> ls -> tag = nd -> rs -> tag = nd -> tag; nd -> ls -> flag = nd -> rs -> flag = 1; nd -> flag = nd -> tag = 0; } } Node *build (ll l, ll r) { Node *nd = newnode (); if (l == r) { nd -> val = a[l]; nd -> tag = nd -> flag = 0; } else { int mid = l + r >> 1; nd -> ls = build (l, mid); nd -> rs = build (mid + 1, r); nd -> update (); } return nd; } void modify (Node *nd, ll l, ll r, ll L, ll R, ll val) { if (L <= l && R >= r) { nd -> val = val * (r - l + 1); nd -> tag = val, nd -> flag = 1; return ; } push_down (nd, l, r); int mid = l + r >> 1; if (L <= mid) modify (nd -> ls, l, mid, L, R, val); if (mid < R) modify (nd -> rs, mid + 1, r, L, R, val); nd -> update (); return ; } ll query (Node *nd, ll l, ll r, ll L, ll R) { if (L <= l && R >= r) return nd -> val; push_down (nd, l, r); int mid = l + r >> 1; ll sww = 0; if (L <= mid) sww += query (nd -> ls, l, mid, L, R); if (mid < R) sww += query (nd -> rs, mid + 1, r, L, R); return sww; } int main () { n = read (), m = read (); for (int i = 1; i <= n; i++) a[i] = read (); init (), root = build (1, n); while (m--) { char opt = getchar (); while (opt != 'M' && opt != 'Q') opt = getchar (); if (opt == 'M') { int x, y, z; x = read (), y = read (), z = read (); modify (root, 1, n, x, y, z); } else { int x, y; x = read (), y = read (); printf ("%lld\n", query (root, 1, n, x, y)); } } return 0; }

描述

给一个长为N的数列，有M次操作，每次操作是以下两种之一：

（1）修改数列中的一个数

（2）求数列中有多少个数比它前面的数都大

输入

第一行两个正整数N和M。 第二行N的整数表示这个数列。 接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来两个整数x和y，表示把x位置的值修改为y；若该字符为'Q'，则表示一个询问操作，求数列中有多少个数比它前面的数都大。

输出

对每一个询问操作单独输出一行，表示答案。

这道题和楼房重建（bzoj2957）是一样的

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e5 + 3; struct Node { int val, sww; Node *ls, *rs; }pool[N << 1], *tail = pool, *root; int n, m, a[N]; int read () { int x = 0, f = 1; char c = getchar (); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar ();} while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar ();} return x * f; } int query (Node *nd, int l, int r, int val) { if (l == r) return nd -> val > val; int mid = l + r >> 1; if (nd -> ls -> val <= val) return query (nd -> rs, mid + 1, r, val); else return nd -> sww - nd -> ls -> sww + query (nd -> ls, l, mid, val); } void update (Node *nd, int l, int r) { nd -> val = max (nd -> ls -> val, nd -> rs -> val); int mid = l + r >> 1; nd -> sww = nd -> ls -> sww + query (nd -> rs, mid + 1, r, nd -> ls -> val); } Node *build (int l, int r) { Node *nd = ++tail; if (l == r) { nd -> val = a[l]; nd -> sww = 1; } else { int mid = l + r >> 1; nd -> ls = build (l, mid); nd -> rs = build (mid + 1, r); update (nd, l, r); } return nd; } void modify (Node *nd, int l, int r, int o, int val) { if (l == r) { nd -> val = val; nd -> sww = 1; return ; } int mid = l + r >> 1; if (o <= mid) modify (nd -> ls, l, mid, o, val); else modify (nd -> rs, mid + 1, r, o, val); update (nd, l, r); return ; } int main () { n = read (), m = read (); for (int i = 1; i <= n; i++) a[i] = read (); root = build (1, n); while (m--) { char opt = getchar (); while (opt != 'M' && opt != 'Q') opt = getchar (); if (opt == 'M') { int x = read (), y = read (); modify (root, 1, n, x, y); } else { printf ("%d\n", root -> sww); } } return 0; }