Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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)#
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月14日 星期日 09时50分10秒
4File Name :code/hdu/5213.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=6E4+7;
34int a[N];
35int n,k;
36int m;
37int sum;
38int ans[N];
39int pos[N];
40int cnt[N];
41struct node
42{
43int l,r;
44int add;
45int id;
46node(){}
47node(int a,int b,int c,int d){l=a,r=b,add=c,id = d;}
48bool operator <(node b)const
49{
50 if (pos[l]==pos[b.l]) return r<b.r;
51 return pos[l]<pos[b.l];
52}
53}q[2*N];
54
55
56void update(int x,int d)
57{
58
59// cout<<"sum1:"<<sum<<endl;
60 cnt[a[x]]+=d;
61 if (k-a[x]>=0)
62 sum = sum + LL(cnt[k-a[x]]*d);
63
64// cout<<"sum2:"<<sum<<endl;
65
66 // cout<<endl;
67
68
69}
70int main()
71{
72 #ifndef ONLINE_JUDGE
73 freopen("code/in.txt","r",stdin);
74#endif
75
76 while (scanf("%d",&n)!=EOF)
77 {
78 ms(ans,0); //多组数据不清空ans数组。。。逗比。。。
79 //因为忘记清空ans数组wa了好久23333
80 scanf("%d",&k);
81 ms(pos,-1);
82 ms(cnt,0);
83 int siz = 175;
84 for ( int i = 1 ; i <= n ; i++)
85 {
86 scanf("%d",&a[i]);
87 pos[i] = (i-1)/siz;
88 }
89
90 scanf("%d",&m);
91 int total = 0;
92 for ( int i = 1 ; i <= m ; i++)
93 {
94 int l1,r1,l2,r2;
95 scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
96 q[++total]=node(r1+1,l2-1,1,i);
97 q[++total]=node(l1,r2,1,i);
98 q[++total]=node(l1,l2-1,-1,i);
99 q[++total]=node(r1+1,r2,-1,i);
100 }
101 sort(q+1,q+total+1);
102 // for ( int i = 1 ; i <= total ; i++) cout<<q[i].l<<" "<<q[i].r<<endl;
103
104 int pl = 1;
105 int pr = 0;
106 sum = 0;
107 int id,l,r;
108 ms(cnt,0);
109
110 for ( int i = 1 ; i <= total ; i++)
111 {
112 id = q[i].id;
113 l = q[i].l;
114 r = q[i].r;
115
116
117 if (pr<r)
118 {
119 for ( int j = pr +1 ; j <= r ; j++)
120 update(j,1);
121 }
122 else
123 {
124 for ( int j = r +1 ; j <= pr; j++)
125 update(j,-1);
126 }
127
128 pr = r;
129
130 if (l<pl)
131 {
132 for ( int j = l; j <= pl-1 ; j++) update(j,1);
133 }
134 else
135 {
136 for ( int j = pl ; j <= l-1 ; j++) update(j,-1);
137 }
138 pl = l;
139
140 // cout<<"sum:"<<sum<<endl;
141 // cout<<"q[i].d:"<<q[i].add<<endl;
142 ans[id] += q[i].add*sum;
143 }
144
145 for ( int i = 1 ; i <= m ; i++) printf("%d\n",ans[i]);
146
147 }
148
149 #ifndef ONLINE_JUDGE
150 fclose(stdin);
151 #endif
152 return 0;
153}