Hdu 5213-Lucky 莫队,容斥原理,分块

showproblem.php?pid=5213

Lucky

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 763 Accepted Submission(s): 249

Problem Description

WLD is always very lucky.His secret is a lucky number

Input

There are multiple cases.(At MOST

Output

For each case:

Print the total of pairs WLD can choose for each question.

Sample Input

5 3 1 2 1 2 3 1 1 2 3 5

Sample Output

Hint

a1+a4=a2+a3=3=K. So we have two pairs of numbers (1,4) and (2,3). Good luck!

Source

BestCoder Round #39 ($)

Recommend

hujie | We have carefully selected several similar problems for you: 5659 5658 5657 5656 5655

题意：给你一个a数列，再给出一些询问，每次询问给两个区间，分别为[l,r]和[u,v]，且1<=l<=r<u<=v<=n，让你从[l,r]中找一个a[i],在[u,v]中找一个a[j],使得a[i]+a[j]＝K，问有多少对。

题解：

好几天没发题解了。。。

来个莫队压压惊。。。

莫队＋容斥

莫队很好想的，主要是如何用容斥。

我们把每组询问的两个区间写出来。

l-----r--------u-----v

|<A>|

|<B>|

|<--C-->|

然后定义f(x,y)为第一个数i在x区间，第二个数j在y区间的a[i]+a[j]=K的方案数。

我们要求的为f(A,B)=f(A+B+C,A+B+C)－f(A+C,A+C)－f(B+C,B+C)+f(C,C)

然后就可以用莫队做了。

这里有些小技巧：在加区间的时候，我们可以把区间的两端点和当前区间的值是加还是减记录下来，这样比较简单。

另外这道题的数组大小好离奇。。。

具体看程序:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define MAXN 30010
 4 #define MAXM 30010
 5 struct node
 6 {
 7     int l,r,id,fh;
 8 }q[MAXM*4];
 9 int a[MAXN],pos[MAXN],sum[MAXN*2],N,ans[MAXM*2];
10 int read()
11 {
12     int s=0,fh=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
15     return s*fh;
16 }
17 void Add(int ll,int rr,int ii,int ff){q[++N].l=ll;q[N].r=rr;q[N].id=ii;q[N].fh=ff;}
18 bool cmp(node aa,node bb)
19 {
20     if(pos[aa.l]==pos[bb.l])return aa.r<bb.r;
21     return aa.l<bb.l;
22 }
23 int main()
24 {
25     int n,k,i,m,block,tot,L,R,U,V;
26     while(scanf("%d",&n)!=EOF)
27     {
28         k=read();
29         for(i=1;i<=n;i++)a[i]=read();
30         m=read();
31         N=0;
32         for(i=1;i<=m;i++)
33         {
34             L=read();R=read();U=read();V=read();
35             Add(L,V,i,1);Add(L,U-1,i,-1);Add(R+1,V,i,-1);Add(R+1,U-1,i,1);
36         }
37         block=(int)sqrt(n);
38         for(i=1;i<=n;i++)pos[i]=(int)(i-1)/block+1;
39         sort(q+1,q+N+1,cmp);
40         memset(ans,0,sizeof(ans));
41         L=1;R=0;
42         tot=0;//当前区间有多少对a[i]+a[j]=k.
43         memset(sum,0,sizeof(sum));//当前区间数字为i的有sum[i]个.
44         for(i=1;i<=N;i++)
45         {
46             while(L<q[i].l)
47             {
48                 sum[a[L]]--;
49                 tot-=sum[k-a[L]];
50                 //sum[a[L]]--;
51                 //if(k==a[L]*2)tot++;
52                 L++;
53             }
54             while(L>q[i].l)
55             {
56                 L--;
57                 tot+=sum[k-a[L]];
58                 sum[a[L]]++;
59             }
60             while(R<q[i].r)
61             {
62                 R++;
63                 tot+=sum[k-a[R]];
64                 sum[a[R]]++;
65             }
66             while(R>q[i].r)
67             {
68                 sum[a[R]]--;
69                 tot-=sum[k-a[R]];
70                 //sum[a[R]]--;
71                 //if(k==a[R]*2)tot++;
72                 R--;
73             }
74             ans[q[i].id]+=q[i].fh*tot;
75         }
76         for(i=1;i<=m;i++)printf("%d
",ans[i]);
77     }
78     fclose(stdin);
79     fclose(stdout);
80     return 0;
81 }