题目链接

题解

只会做\(70\)分的\(O(nlog^2n)\)

如果本来就在区间内的人是不用动的，区间右边的人往区间最右的那些空位跑，区间左边的人往区间最左的那些空位跑

找到这些空位就用二分 + 主席树

理应可以在主席树上的区间二分而做到\(O(nlogn)\)，但是写不出来，先留着坑

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define REP(i,n) for (register int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,long long int>(a,b)

#define cp pair<int,long long int>

#define LL long long int

using namespace std;

const int maxn = 500005,maxm = 11000005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int N,n,m,rt[maxn];

int ls[maxm],rs[maxm],num[maxm],cnt;

LL sum[maxm];

void modify(int& u,int pre,int l,int r,int pos){

	u = ++cnt;

	sum[u] = sum[pre] + pos; num[u] = num[pre] + 1;

	ls[u] = ls[pre]; rs[u] = rs[pre];

	if (l == r) return;

	int mid = l + r >> 1;

	if (mid >= pos) modify(ls[u],ls[pre],l,mid,pos);

	else modify(rs[u],rs[pre],mid + 1,r,pos);

}

int q_num(int u,int v,int l,int r,int L,int R){

	if (l >= L && r <= R) return num[u] - num[v];

	int mid = l + r >> 1;

	if (mid >= R) return q_num(ls[u],ls[v],l,mid,L,R);

	if (mid < L) return q_num(rs[u],rs[v],mid + 1,r,L,R);

	return q_num(ls[u],ls[v],l,mid,L,R) + q_num(rs[u],rs[v],mid + 1,r,L,R);

}

LL q_sum(int u,int v,int l,int r,int L,int R){

	if (l >= L && r <= R) return sum[u] - sum[v];

	int mid = l + r >> 1;

	if (mid >= R) return q_sum(ls[u],ls[v],l,mid,L,R);

	if (mid < L) return q_sum(rs[u],rs[v],mid + 1,r,L,R);

	return q_sum(ls[u],ls[v],l,mid,L,R) + q_sum(rs[u],rs[v],mid + 1,r,L,R);

}

inline LL S(int l,int r){

	return 1ll * (l + r) * (r - l + 1) / 2;

}

inline LL q_pre(int u,int v,int L,int R,int k){

	int ll = L,rr = R,mid; LL a;

	while (ll < rr){

		mid = ll + rr >> 1;

		a = q_num(u,v,1,N,L,mid);

		if ((mid - L + 1) - a >= k) rr = mid;

		else ll = mid + 1;

	}

	a = q_sum(u,v,1,N,L,ll);

	return S(L,ll) - a;

}

inline LL q_post(int u,int v,int L,int R,int k){

	int ll = L,rr = R,mid,a;

	while (ll < rr){

		mid = ll + rr + 1 >> 1;

		a = q_num(u,v,1,N,mid,R);

		if ((R - mid + 1) - a >= k) ll = mid;

		else rr = mid - 1;

	}

	a = q_sum(u,v,1,N,mid,R);

	return S(ll,R) - a;

}

void work(){

	int l,r,L,R,a,s; LL ans,b;

	while (m--){

		l = read(); r = read(); L = read(); R = L + r - l; ans = 0;

		if (L > 1){

			a = q_num(rt[r],rt[l - 1],1,N,1,L - 1);

			if (a){

				s = q_sum(rt[r],rt[l - 1],1,N,1,L - 1);

				b = q_pre(rt[r],rt[l - 1],L,R,a);

				ans += b - s;

			}

		}

		a = q_num(rt[r],rt[l - 1],1,N,R + 1,N);

		if (a){

			s = q_sum(rt[r],rt[l - 1],1,N,R + 1,N);

			b = q_post(rt[r],rt[l - 1],L,R,a);

			ans += s - b;

		}

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

	}

}

int main(){

	n = read(); m = read(); N = 1000000 + n + 1; int x;

	REP(i,n){

		x = read(),modify(rt[i],rt[i - 1],1,N,x);

	}

	work();

	return 0;

}

巴特西

洛谷P4559 [JSOI2018]列队【70分二分 + 主席树】

题目链接

题解

最新文章

热门文章

巴特西

洛谷P4559 [JSOI2018]列队 【70分二分 + 主席树】

题目链接

题解

最新文章

热门文章

洛谷P4559 [JSOI2018]列队【70分二分 + 主席树】