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}