HDU 5213：Lucky (莫队 + 容斥原理)

题目描述:

初始有一个序列 a 和一个正数 K ,每次询问 : 分别从区间 [l,r] ,[u,v] 中各选一个数字,其值等于K的方案有多少？

题解：

感谢大佬提供的思路

https://www.cnblogs.com/HDUjackyan/p/8996172.html

因为求的是区间内的答案，可以用莫队，通过莫队算法，可以很容易求出一个区间内的答案，但这题同时有两个区间，直接做不好做，需要用容斥原理。

根据题目中描述，u,v一定在l,r的右边。在一条线上是4个点降这条线划分为5个区间，中间3个区间对我们有用。

求用到左区间 x和用到右区间 y 的答案不好求，但求 [l,v] 内的答案很好求。

考虑容斥原理，我们用[l,v] 内的答案 扣掉没有用到左区间和右区间的答案总数，就是用左区间和右区间的答案了。

将询问区间分成4个区间，答案F = F[l,v] - F[l,u - 1] - F[r + 1,u] + F[r + 1,u - 1]；这样问题转化成了单个区间的求解，然后跑莫队算法依次求出来对最终答案进行加权。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e4 + 100;
int k,n,m,a[maxn],cnt[maxn],ans[maxn],block,L,R,res;
struct ss{
	int l,r,id,type;
}qes[maxn * 4];
bool cmp(ss a,ss b) {
	return a.l / block == b.l / block ? a.r < b.r : a.l < b.l;
}
void move(int l,int r) {
	while(L > l) {
		L--;
		res -= cnt[a[L]] * (cnt[k - a[L]]);
		cnt[a[L]]++;
		res += cnt[a[L]] * (cnt[k - a[L]]);
	}
	while(R < r) {
		R++;
		res -= cnt[a[R]] * (cnt[k - a[R]]);
		cnt[a[R]]++;
		res += cnt[a[R]] * (cnt[k - a[R]]);		
	}
	while(L < l) {
		res -= cnt[a[L]] * (cnt[k - a[L]]);
		cnt[a[L]]--;
		res += cnt[a[L]] * (cnt[k - a[L]]);
		L++;
	}
	while(R > r) {
		res -= cnt[a[R]] * (cnt[k - a[R]]);
		cnt[a[R]]--;
		res += cnt[a[R]] * (cnt[k - a[R]]);		
		R--;	
	}
}
int main() {
	while(scanf("%d",&n) != EOF) {
		scanf("%d",&k);
		memset(cnt,0,sizeof cnt);
		memset(ans,0,sizeof ans);
		for(int i = 1; i <= n; i++) {
			scanf("%d",&a[i]);
		}
		scanf("%d",&m);
		for(int i = 1; i <= m; i++) {
			int u,v,l,r;
			scanf("%d%d%d%d",&l,&r,&u,&v);
			qes[4 * i - 3] = (ss) {l,v,i,1};
			qes[4 * i - 2] = (ss) {l,u - 1,i,-1};
			qes[4 * i - 1] = (ss) {r + 1,v,i,-1};
			qes[4 * i] = (ss) {r + 1,u - 1,i,1};
		}
		block = sqrt(n);
		sort(qes + 1,qes + 4 * m + 1,cmp);
		cnt[a[1]] = L = R = 1;
		for(int i = 1; i <= 4 * m; i++) {
			int p = qes[i].id,t = qes[i].type;
			move(qes[i].l,qes[i].r);
			ans[p] += res * t; 
		}
		for(int i = 1; i <= m; i++) {
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}