首页 > 代码库 > bzoj4889
bzoj4889
http://www.lydsy.com/JudgeOnline/problem.php?id=4889
人傻常数大 bzoj上跑不过 洛谷上能过两到三个点
我写的是树套树啊 怎么跑的比分块还慢
每次可以发现交换两个点 只对他们中间的点有影响 所以我们只用计算比x小的数的和 比x大的数的和 比y小的数的和 比y大的数的和 然后计算一下就可以了 很明显可以用各种数据结构维护
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 4000010; const ll mod = 1000000007; int n, m, cnt; ll ans; int q[N]; inline 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; } struct BIT { ll tree[N], count[N]; int lowbit(int i) { return i & (-i); } void update(int pos, ll delta) { for(int i = pos; i <= 50001; i += lowbit(i)) { tree[i] = (tree[i] + delta) % mod; ++count[i]; } } ll query(int pos, ll delta) { ll ret1 = 0, ret2 = 0; for(int i = pos; i; i -= lowbit(i)) { ret1 = (ret1 + tree[i]) % mod; ret2 += count[i]; } ret1 = (ret1 + ret2 * delta) % mod; return ret1; } } B; struct data { int a; ll v; } tree[N], a[N]; namespace splaytree { int fa[N], child[N][2], root[N]; ll size[N], num[N], sum[N]; void update(int x) { size[x] = num[x] + size[child[x][0]] + size[child[x][1]]; sum[x] = (tree[x].v * num[x] + sum[child[x][0]] + sum[child[x][1]]) % mod; } void zig(int x) { int y = fa[x]; fa[x] = fa[y]; child[fa[x]][child[fa[x]][1] == y] = x; child[y][0] = child[x][1]; fa[child[x][1]] = y; fa[y] = x; child[x][1] = y; update(y); update(x); } void zag(int x) { int y = fa[x]; fa[x] = fa[y]; child[fa[x]][child[fa[x]][1] == y] = x; child[y][1] = child[x][0]; fa[child[x][0]] = y; fa[y] = x; child[x][0] = y; update(y); update(x); } void splay(int x, int t, int pos) { while(fa[x] != t) { int y = fa[x], z = fa[y]; if(z == t) { child[y][0] == x ? zig(x) : zag(x); break; } else if(y == child[z][0] && x == child[y][0]) { zig(y); zig(x); } else if(y == child[z][1] && x == child[y][1]) { zag(y); zag(x); } else if(y == child[z][0] && x == child[y][1]) { zag(x); zig(x); } else if(y == child[z][1] && x == child[y][0]) { zig(x); zag(x); } } if(!t) root[pos] = x; update(root[pos]); } void up(int x) { while(x) { update(x); x = fa[x]; } } ll getbig(int pos, data &k) { int now = root[pos]; ll ret = 0; while(now) { if(tree[now].a > k.a) { ret = (ret + k.v + tree[now].v) % mod; ret = (ret + k.v * size[child[now][1]] + sum[child[now][1]]) % mod; now = child[now][0]; } else now = child[now][1]; } return ret; } ll getsmall(int pos, data &k) { int now = root[pos]; ll ret = 0; while(now) { if(tree[now].a < k.a) { ret = (ret + k.v + tree[now].v) % mod; ret = (ret + k.v * size[child[now][0]] + sum[child[now][0]]) % mod; now = child[now][1]; } else now = child[now][0]; } return ret; } int find(int x, data &k) { for(x = root[x]; x; x = child[x][k.a > tree[x].a]) if(tree[x].a == k.a) return x; } void del(int pos, int x) { splay(x, 0, pos); if(num[x] > 1) { --num[x]; update(x); return; } if(child[x][0] * child[x][1] == 0) { root[pos] = child[x][0] + child[x][1]; fa[root[pos]] = 0; child[x][0] = child[x][1] = fa[x] = 0; return; } int now = child[x][1]; while(child[now][0]) now = child[now][0]; fa[child[x][0]] = now; child[now][0] = child[x][0]; root[pos] = child[x][1]; fa[root[pos]] = 0; up(child[x][0]); child[x][0] = child[x][1] = num[x] = size[x] = fa[x] = 0; splay(now, 0, pos); } void insert(int pos, data &k) { int now = root[pos]; if(!root[pos]) { root[pos] = ++cnt; tree[cnt] = k; size[cnt] = num[cnt] = 1; sum[cnt] = k.v; return; } while(1) { if(tree[now].a == k.a) { ++num[now]; up(now); break; } if(!child[now][k.a > tree[now].a]) { child[now][k.a > tree[now].a] = ++cnt; tree[cnt] = k; size[cnt] = num[cnt] = 1; fa[cnt] = now; sum[cnt] = k.v; up(cnt); splay(cnt, 0, pos); break; } now = child[now][k.a > tree[now].a]; } } } using namespace splaytree; namespace segmenttree { void update(int l, int r, int x, int pos, data &k) { if(l == r) { root[x] = ++cnt; tree[cnt] = k; num[cnt] = size[cnt] = 1; sum[cnt] = k.v; return; } int mid = (l + r) >> 1; if(pos <= mid) update(l, mid, x << 1, pos, k); else update(mid + 1, r, x << 1 | 1, pos, k); int t = find(x, a[pos]); del(x, t); insert(x, k); } void build(int l, int r, int x) { if(l == r) { root[x] = ++cnt; num[cnt] = size[cnt] = 1; tree[cnt] = a[l]; sum[cnt] = a[l].v; return; } int mid = (l + r) >> 1; build(l, mid, x << 1); build(mid + 1, r, x << 1 | 1); for(int i = l; i <= r; ++i) insert(x, a[i]); } ll querybig(int l, int r, int x, int a, int b, data &k) { if(l > b || r < a) return 0; if(l >= a && r <= b) return getbig(x, k) % mod; int mid = (l + r) >> 1; return ((querybig(l, mid, x << 1, a, b, k) + querybig(mid + 1, r, x << 1 | 1, a, b, k)) % mod); } ll querysmall(int l, int r, int x, int a, int b, data &k) { if(l > b || r < a) return 0; if(l >= a && r <= b) return getsmall(x, k) % mod; int mid = (l + r) >> 1; return ((querysmall(l, mid, x << 1, a, b, k) + querysmall(mid + 1, r, x << 1 | 1, a, b, k)) % mod); } } using namespace segmenttree; int main() { n = read(); m = read(); for(int i = 1; i <= n; ++i) { a[i].a = read(); a[i].v = read(); ans = ((ans + B.query(50001, a[i].v) - B.query(a[i].a, a[i].v)) % mod + mod) % mod; B.update(a[i].a, a[i].v); } build(1, n, 1); while(m--) { int x, y; x = read(); y = read(); if(x > y) swap(x, y); if(x == y) { printf("%lld\n", ans); continue; } if(a[x].a < a[y].a) ans += a[x].v + a[y].v; else ans -= a[x].v + a[y].v; ll a1 = querybig(1, n, 1, x + 1, y - 1, a[x]); ll a2 = querysmall(1, n, 1, x + 1, y - 1, a[x]); ll a3 = querysmall(1, n, 1, x + 1, y - 1, a[y]); ll a4 = querybig(1, n, 1, x + 1, y - 1, a[y]); ans = ((ans + a1 - a2 + a3 - a4) % mod + mod) % mod; update(1, n, 1, x, a[y]); update(1, n, 1, y, a[x]); swap(a[x], a[y]); printf("%lld\n", ans); } return 0; }
bzoj4889
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。