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 = ;
const ll mod = ;
int n, m, cnt;
ll ans;
int q[N];
inline int read()
{
int x = , f = ; char c = getchar();
while(c < '' || c > '')
{
if(c == '-') f = -;
c = getchar();
}
while(c >= '' && c <= '')
{
x = x * + c - '';
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 <= ; i += lowbit(i))
{
tree[i] = (tree[i] + delta) % mod;
++count[i];
}
}
ll query(int pos, ll delta)
{
ll ret1 = , ret2 = ;
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][], root[N];
ll size[N], num[N], sum[N];
void update(int x)
{
size[x] = num[x] + size[child[x][]] + size[child[x][]];
sum[x] = (tree[x].v * num[x] + sum[child[x][]] + sum[child[x][]]) % mod;
}
void zig(int x)
{
int y = fa[x];
fa[x] = fa[y];
child[fa[x]][child[fa[x]][] == y] = x;
child[y][] = child[x][];
fa[child[x][]] = y;
fa[y] = x;
child[x][] = y;
update(y);
update(x);
}
void zag(int x)
{
int y = fa[x];
fa[x] = fa[y];
child[fa[x]][child[fa[x]][] == y] = x;
child[y][] = child[x][];
fa[child[x][]] = y;
fa[y] = x;
child[x][] = 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][] == x ? zig(x) : zag(x);
break;
}
else if(y == child[z][] && x == child[y][]) { zig(y); zig(x); }
else if(y == child[z][] && x == child[y][]) { zag(y); zag(x); }
else if(y == child[z][] && x == child[y][]) { zag(x); zig(x); }
else if(y == child[z][] && x == child[y][]) { 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 = ;
while(now)
{
if(tree[now].a > k.a)
{
ret = (ret + k.v + tree[now].v) % mod;
ret = (ret + k.v * size[child[now][]] +
sum[child[now][]]) % mod;
now = child[now][];
}
else now = child[now][];
}
return ret;
}
ll getsmall(int pos, data &k)
{
int now = root[pos];
ll ret = ;
while(now)
{
if(tree[now].a < k.a)
{
ret = (ret + k.v + tree[now].v) % mod;
ret = (ret + k.v * size[child[now][]] +
sum[child[now][]]) % mod;
now = child[now][];
}
else now = child[now][];
}
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, , pos);
if(num[x] > )
{
--num[x];
update(x);
return;
}
if(child[x][] * child[x][] == )
{
root[pos] = child[x][] + child[x][];
fa[root[pos]] = ;
child[x][] = child[x][] = fa[x] = ;
return;
}
int now = child[x][];
while(child[now][]) now = child[now][];
fa[child[x][]] = now;
child[now][] = child[x][];
root[pos] = child[x][];
fa[root[pos]] = ;
up(child[x][]);
child[x][] = child[x][] = num[x] = size[x]
= fa[x] = ;
splay(now, , pos);
}
void insert(int pos, data &k)
{
int now = root[pos];
if(!root[pos])
{
root[pos] = ++cnt;
tree[cnt] = k;
size[cnt] = num[cnt] = ;
sum[cnt] = k.v;
return;
}
while()
{
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] = ;
fa[cnt] = now;
sum[cnt] = k.v;
up(cnt);
splay(cnt, , 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] = ;
sum[cnt] = k.v;
return;
}
int mid = (l + r) >> ;
if(pos <= mid) update(l, mid, x << , pos, k);
else update(mid + , r, x << | , 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] = ;
tree[cnt] = a[l];
sum[cnt] = a[l].v;
return;
}
int mid = (l + r) >> ;
build(l, mid, x << );
build(mid + , r, x << | );
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 ;
if(l >= a && r <= b) return getbig(x, k) % mod;
int mid = (l + r) >> ;
return ((querybig(l, mid, x << , a, b, k) +
querybig(mid + , r, x << | , a, b, k)) % mod);
}
ll querysmall(int l, int r, int x, int a, int b, data &k)
{
if(l > b || r < a) return ;
if(l >= a && r <= b) return getsmall(x, k) % mod;
int mid = (l + r) >> ;
return ((querysmall(l, mid, x << , a, b, k) +
querysmall(mid + , r, x << | , a, b, k)) % mod);
}
} using namespace segmenttree;
int main()
{
n = read(); m = read();
for(int i = ; i <= n; ++i)
{
a[i].a = read(); a[i].v = read();
ans = ((ans + B.query(, a[i].v) - B.query(a[i].a, a[i].v)) % mod + mod) % mod;
B.update(a[i].a, a[i].v);
}
build(, n, );
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(, n, , x + , y - , a[x]);
ll a2 = querysmall(, n, , x + , y - , a[x]);
ll a3 = querysmall(, n, , x + , y - , a[y]);
ll a4 = querybig(, n, , x + , y - , a[y]);
ans = ((ans + a1 - a2 + a3 - a4) % mod + mod) % mod;
update(, n, , x, a[y]);
update(, n, , y, a[x]);
swap(a[x], a[y]);
printf("%lld\n", ans);
}
return ;
}
