【LOJ2254】【SNOI2017】一个简单的询问

Author Avatar
q234rty 8月 02, 2017

莫队算法即可。

本题粗看似乎无从下手，考虑将一个询问拆成多个前缀询问。

设 f(x,y)=ans(1,x,1,y) , g(x,y)=get(1,x,y) ,我们有

\begin{aligned} ans(l1,r1,l2,r2) & =\sum_{x=0}^{\infty}(g(r1,x)-g(l1-1,x))\times (g(r2,x)-g(l2-1,x))\\ & =\sum_{x=0}^{\infty}g(r1,x)\times g(r2,x)-g(r1,x)\times g(l2-1,x)\\ & -g(l1-1,x)\times g(r2,x)+g(l1-1,x)\times g(l2-1,x)\\ & =f(r1,r2)-f(r1,l2-1)-f(l1-1,r2)+f(l1-1,l2-1) \end{aligned}

于是用莫队计算 f 即可。

用两个数组分别维护两个前缀中每个数的出现次数，增删数时可以 O(1) 更新答案。

时间复杂度 O(n \sqrt n) 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
	#ifdef LOCAL
		freopen("2254.txt","r",stdin);
	#endif
	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
	bufpos=0;
}
#if NEG
int readint(){
	bool isneg;
	int val=0;
	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
	bufpos+=(isneg=buf[bufpos]=='-');
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return isneg?-val:val;
}
#else
int readint(){
	int val=0;
	for(;!isdigit(buf[bufpos]);bufpos++);
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return val;
}
#endif
char readchar(){
	for(;isspace(buf[bufpos]);bufpos++);
	return buf[bufpos++];
}
int readstr(char* s){
	int cur=0;
	for(;isspace(buf[bufpos]);bufpos++);
	for(;!isspace(buf[bufpos]);bufpos++)
		s[cur++]=buf[bufpos];
	s[cur]='\0';
	return cur;
}
ll ans[50001],now;
int a[50001],cnt[2][50001],pl[50001];
struct query{
	int p,sgn,l1,l2;
	bool operator <(const query& rhs)const{
		return pl[l1]!=pl[rhs.l1]?pl[l1]<pl[rhs.l1]:l2<rhs.l2;
	}
}q[200001];
void update(int p,int v,int sgn){
	now+=sgn*cnt[p^1][v];
	cnt[p][v]+=sgn;
}
int main(){
	init();
	int n=readint(),cur=0;
	for(int i=1;i<=n;i++)
		a[i]=readint();
	int m=readint();
	for(int i=1;i<=m;i++){
		int l1=readint()-1,r1=readint(),l2=readint()-1,r2=readint();
		if (l1)
			q[++cur]=(query){i,-1,l1,r2};
		if (l2)
			q[++cur]=(query){i,-1,l2,r1};
		if (l1 && l2)
			q[++cur]=(query){i,1,l1,l2};
		q[++cur]=(query){i,1,r1,r2};
	}
	int sz=sqrt(n)+0.5;
	for(int i=1;i<=n;i++)
		pl[i]=(i-1)/sz+1;
	sort(q+1,q+cur+1);
	int l1=0,l2=0;
	for(int i=1;i<=cur;i++){
		while(l1<q[i].l1)
			update(0,a[++l1],1);
		while(l1>q[i].l1)
			update(0,a[l1--],-1);
		while(l2<q[i].l2)
			update(1,a[++l2],1);
		while(l2>q[i].l2)
			update(1,a[l2--],-1);
		ans[q[i].p]+=now*q[i].sgn;
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2017/08/02/loj2254/

隐藏