hdu 5213 lucky （莫队算法）
http://acm.hdu.edu.cn/showproblem.php?pid=5213 题意：n个数，m个查询，每个查询由4个数l1,r1,l2,r2构成，询问分别从[l1,r1]和[l2,r2]中各取一个数，和为给定的常数k的方案数。
思路：首先分别由两个区间取数不好搞，我们可以用容斥原理对区间变换。这是这道题最关键的一步。
官方题解：这道题需要一些莫队算法的知识 定义记号f(A,B)f(A,B)表示询问区间A，B时的答案 用记号＋表示集合的并 利用莫队算法我们可以计算出任意f(A,A)f(A,A)的值 不妨假设A=[l1,r1],B=[l2,r2],C=[r1+1,l2-1]A=[l1,r1],B=[l2,r2],C=[r1+1,l2−1]容易知道（并没有很容易）f(A,B)=f(A+B+C,A+B+C)+f(C,C)-f(A+C,A+C)-f(C+B,C+B)f(A,B)=f(A+B+C,A+B+C)+f(C,C)−f(A+C,A+C)−f(C+B,C+B) 因此一个询问被拆成四个可以用莫队算法做的询问 总的时间复杂度为O(msqrt(n))O(msqrt(n))
然后就是莫队算法的内容**。值得一提的是，被拆成的四个子询问不必做四次莫队，可以合在一起，因为每一次询问对答案的贡献都不会受顺序影响，而且这样用时更短。**
然后初始构造的时候用构造函数比赋值要方便许多。
还要记得多组数据记得清空各种数组。。。（因为忘记清空ans数组wa到死。。。）
最最关键的是，对于求两个数a+b==k这类问题（不一定是加，就是和两个数满足一个关系的时候），我们可以转换思维。a==k-b.也就是统计的时候是cnt[b]++,更新答案的时候，由于现在是b,我需要找有多少个a，也就是多少个k-b,所以是ans+=cnt[k-b];（要注意保证k-b>0)
/* ***********************************************
Author :111qqz
Created Time :2016年02月14日 星期日 09时50分10秒
File Name :code/hdu/5213.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=6E4+7;
7int a[N];
8int n,k;
9int m;
10int sum;
11int ans[N];
12int pos[N];
13int cnt[N];
14struct node
15{
16int l,r;
17int add;
18int id;
19node(){}
20node(int a,int b,int c,int d){l=a,r=b,add=c,id = d;}
21bool operator <(node b)const
22{
23 if (pos[l]==pos[b.l]) return r<b.r;
24 return pos[l]<pos[b.l];
25}
26}q[2*N];
void update(int x,int d)
{
1// cout<<"sum1:"<<sum<<endl;
2 cnt[a[x]]+=d;
3 if (k-a[x]>=0)
4 sum = sum + LL(cnt[k-a[x]]*d);
// cout<<"sum2:"<<sum<<endl;
// cout<<endl;
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("code/in.txt","r",stdin);
6#endif
1 while (scanf("%d",&n)!=EOF)
2 {
3 ms(ans,0); //多组数据不清空ans数组。。。逗比。。。
4 //因为忘记清空ans数组wa了好久23333
5 scanf("%d",&k);
6 ms(pos,-1);
7 ms(cnt,0);
8 int siz = 175;
9 for ( int i = 1 ; i <= n ; i++)
10 {
11 scanf("%d",&a[i]);
12 pos[i] = (i-1)/siz;
13 }
1 scanf("%d",&m);
2 int total = 0;
3 for ( int i = 1 ; i <= m ; i++)
4 {
5 int l1,r1,l2,r2;
6 scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
7 q[++total]=node(r1+1,l2-1,1,i);
8 q[++total]=node(l1,r2,1,i);
9 q[++total]=node(l1,l2-1,-1,i);
10 q[++total]=node(r1+1,r2,-1,i);
11 }
12 sort(q+1,q+total+1);
13 // for ( int i = 1 ; i <= total ; i++) cout<<q[i].l<<" "<<q[i].r<<endl;
1 int pl = 1;
2 int pr = 0;
3 sum = 0;
4 int id,l,r;
5 ms(cnt,0);
1 for ( int i = 1 ; i <= total ; i++)
2 {
3 id = q[i].id;
4 l = q[i].l;
5 r = q[i].r;
1 if (pr<r)
2 {
3 for ( int j = pr +1 ; j <= r ; j++)
4 update(j,1);
5 }
6 else
7 {
8 for ( int j = r +1 ; j <= pr; j++)
9 update(j,-1);
10 }
pr = r;
1 if (l<pl)
2 {
3 for ( int j = l; j <= pl-1 ; j++) update(j,1);
4 }
5 else
6 {
7 for ( int j = pl ; j <= l-1 ; j++) update(j,-1);
8 }
9 pl = l;
1 // cout<<"sum:"<<sum<<endl;
2 // cout<<"q[i].d:"<<q[i].add<<endl;
3 ans[id] += q[i].add*sum;
4 }
for ( int i = 1 ; i <= m ; i++) printf("%d\n",ans[i]);
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}