luogu3759 [TJOI2017]不勤劳的图书管理员

分块+权值逆序对
#include <algorithm>

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long ll;

int n, m, uu, vv, blc, bel[50005], ans, ccnt[50005], cval[500005], num[255];

int sum[255][255];

const int mod=1e9+7;

struct Node{

	int idx, val;

}nd[50005], qwq[255][255];

bool cmp1(Node x, Node y){

	return x.idx<y.idx;

}

int lb(int x){

	return x&-x;

}

void bitAdd(int x, int y){

	for(int i=x; i<=n; i+=lb(i)){

		ccnt[i]++;

		cval[i] = (cval[i] + y) % mod;

	}

}

int bitQuery(int x, int &qaq){

	int re=0;

	for(int i=x; i; i-=lb(i)){

		qaq += ccnt[i];

		re = (re + cval[i]) % mod;

	}

	return re;

}

int query1(int l, int r, Node x){

	if(l>r)	return 0;

	int re=0;

	if(bel[l]==bel[r]){

		for(int i=l; i<=r; i++)

			if(nd[i].idx>x.idx)

				re = (re + (nd[i].val+x.val)%mod) % mod;

	}

	else{

		for(int i=bel[l]+1; i<=bel[r]-1; i++){

			int pos=lower_bound(qwq[i]+1, qwq[i]+1+num[i], x, cmp1)-qwq[i];

			int cnt=num[i]-pos+1;

			re = (re + (ll)cnt * x.val) % mod;

			re = (re + ((sum[i][num[i]] - sum[i][pos-1])%mod + mod)%mod) % mod;

		}

		for(int i=l; i<=bel[l]*blc; i++)

			if(nd[i].idx>x.idx)

				re = (re + (nd[i].val+x.val)%mod) % mod;

		for(int i=(bel[r]-1)*blc+1; i<=r; i++)

			if(nd[i].idx>x.idx)

				re = (re + (nd[i].val+x.val)%mod) % mod;

	}

	return re;

}

int query2(int l, int r, Node x){

	if(l>r)	return 0;

	int re=0;

	if(bel[l]==bel[r]){

		for(int i=l; i<=r; i++)

			if(nd[i].idx<x.idx)

				re = (re + (nd[i].val+x.val)%mod) % mod;

	}

	else{

		for(int i=bel[l]+1; i<=bel[r]-1; i++){

			int pos=lower_bound(qwq[i]+1, qwq[i]+1+num[i], x, cmp1)-qwq[i];

			int cnt=pos-1;

			re = (re + (ll)cnt * x.val) % mod;

			if(cnt)	re = (re + sum[i][cnt]) % mod;

		}

		for(int i=l; i<=bel[l]*blc; i++)

			if(nd[i].idx<x.idx)

				re = (re + (nd[i].val+x.val)%mod) % mod;

		for(int i=(bel[r]-1)*blc+1; i<=r; i++)

			if(nd[i].idx<x.idx)

				re = (re + (nd[i].val+x.val)%mod) % mod;

	}

	return re;

}

void gouzao(int x){

	num[x] = 0;

	for(int i=(x-1)*blc+1; i<=min(x*blc, n); i++)

		qwq[x][++num[x]] = nd[i];

	sort(qwq[x]+1, qwq[x]+1+num[x], cmp1);

	for(int i=1; i<=num[x]; i++){

		sum[x][i] = qwq[x][i].val;

		sum[x][i] = (sum[x][i] + sum[x][i-1]) % mod;

	}

}

int main(){

	cin>>n>>m;

	blc = sqrt(n);

	for(int i=1; i<=n; i++){

		scanf("%d %d", &nd[i].idx, &nd[i].val);

		bel[i] = (i - 1) / blc + 1;

	}

	for(int i=1; i<=n; i++)

		qwq[bel[i]][++num[bel[i]]] = nd[i];

	for(int i=1; i<=bel[n]; i++)

		gouzao(i);

	for(int i=1; i<=n; i++){

		int tmp1=0, tmp2=0;

		ans = (ans + bitQuery(n, tmp1) - bitQuery(nd[i].idx, tmp2)) % mod;

		ans = (ans + (ll)(tmp1-tmp2)*nd[i].val) % mod;

		bitAdd(nd[i].idx, nd[i].val);

	}

	while(m--){

		scanf("%d %d", &uu, &vv);

		if(uu>vv)	swap(uu, vv);

		ans = (ans - query1(uu+1, vv-1, nd[vv]) + mod) % mod;

		ans = (ans - query2(uu+1, vv-1, nd[uu]) + mod) % mod;

		if(nd[uu].idx>nd[vv].idx)	ans = (ans - (nd[uu].val+nd[vv].val)%mod + mod) % mod;

		swap(nd[uu], nd[vv]);

		gouzao(bel[uu]); gouzao(bel[vv]);

		ans = (ans + query1(uu+1, vv-1, nd[vv])) % mod;

		ans = (ans + query2(uu+1, vv-1, nd[uu])) % mod;

		if(nd[uu].idx>nd[vv].idx)	ans = (ans + (nd[uu].val+nd[vv].val)%mod) % mod;

		printf("%d\n", ans);

	}

	return 0;

}
巴特西

luogu3759 [TJOI2017]不勤劳的图书管理员

最新文章

热门文章
