莫队算法相关

分块?

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 17   Accepted Submission(s) : 6

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给定n个数,记为ai(1<=i <= n),求区间内某两个数和为给定的sum的对数。

Input

  第一行输入整数T,表示共有T组.
  接下来共T组,首先输入n,sum分别表示共n个数以及给定的和,再下一行依次输入n个数ai,然后输入一个q,表示共有q个询问,接下来q行每行输入l,r,表示要求的是区间[l,r].

范围:
T<=20
n <= 20000,sum <= 20000
1 <= ai < sum
q <= 20000,1<= l < r <= n

Output

  输出q行,回答每个询问的值.

Sample Input

1
4 4
1 2 2 3
3
1 2
2 3
1 4

Sample Output

0
1
2

Source

test

关于莫队算法,个人觉得这篇讲的比较通俗易懂,关于复杂度上界O(n^1.5)也证明的比较详细。。(大致上来说就是按左边界分块且每块内按右边界排列之后,将每次r的转移最坏O(n),变成一个块内的询问转移完毕最坏O(n),l的转移总复杂度可以类似分析)
真正的莫队算法是要求最小曼哈顿生成树的,但是其实有一种简洁的分块方法,具体见上面链接中的文章
其实突然发现自己以前是碰到过这种分块题目的,在一片论文中讲了一种支持修改的动态rmq算法,就是分块的,每次询问时sqrt(n),自己还写了模板,坑爹啊,全忘光了。。
这里还是简述下怎么分块:将长度为n的数列划分成每段长为sqrt(n)的一些段,这样可以保证复杂度上界是O(n^1.5)(当然前提是单步转移是O(1),如果是lgn,那么总复杂度是O((n^1.5)*lgn))。证明见上面说的文章,里面讲的很清楚。
这道题的话,数的范围在20000以内,所以可以用一个数组cnt[i],表示数i出现了几次。这样从(l,r)转移到(l,r+1)是O(1)的。像这种单步转移能做到O(1)或者O(lgn)的,都可以用莫队算法来搞。然后先O(n)算出第一个询问的答案,之后转移到第二个询问的时候,要注意如果是较少一个数,也就是差不多(l,r)->(l+1,r)这种转移类型,那么如果data[l]等于sum-data[l]时注意特判,因为这时候减少的对数不是cnt[sum-data[l]],而是cnt[sum-data[l]]-1。(试想,现在有3个2,sum为4,那么有3对数它们的和为4,然后减少一个2,显然减少了2对,而不是3对)

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct Query{
    int l,r,g,num,ans;
}Q;
Q q[20010];
int n,sum,data[20010],m;
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
bool cmp2(Q a,Q b)
{
    return a.num<b.num;
}
int cnt[20010];
void cal(Q &a,Q &b)
{
    int i,tmp=a.ans;
    int l1=a.l,r1=a.r,l2=b.l,r2=b.r;
    if(r1<=l2 || r2<=l1)
    {
        for(i=l1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=l2;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l1<=l2 && l2<=r1 && r1<=r2)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l2<=l1 && l1<=r2 && r2<=r1)
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else if(l1<=l2 && r2<=r1)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    b.ans=tmp;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&sum);
        memset(cnt,0,sizeof(cnt));
        int len=(int)sqrt(n*1.0);
        //int cnt=(len*len==n?len:len+1);
        for(i=1;i<=n;i++) scanf("%d",&data[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].g=q[i].l/len+1;
            q[i].num=i;q[i].ans=0;
        }
        sort(q+1,q+1+m,cmp);
        for(i=q[1].l;i<=q[1].r;i++) q[1].ans+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=2;i<=m;i++) cal(q[i-1],q[i]);
        sort(q+1,q+1+m,cmp2);
        for(i=1;i<=m;i++) printf("%d\n",q[i].ans);



    }
    return 0;
}

其他题目:
bzoj2038
poj3241
WC 2013 糖果公园
UVALive 3662 Another Minimum Spanning Tree
hdu5213

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29469

One thought on “莫队算法相关

  1. Pingback: stroll with the moon | cf375D Tree and Queries

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>