分块? 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 题意: 给定N个数,记为ai(1<=i <= N),求区间内某两个数和为给定的M的对数。一共Q次询问 题解: 现在知道[l,r]的答案ans,可以O(1)得出[l,r+1]的答案 c[i]表示现在值为i的数有几个,那么a[r+1]=x对答案贡献了c[M-x],所以[l,r+1]的答案就是ans+c[M-x] 同理可以O(1)得到[l-1,r]的答案
  1. void insert(int x){
  2.     x=a[x];
  3.     ans+=c[M-x];
  4.     ++c[x];
  5. }
现在知道[l,r]的答案ans,可以O(1)得出[l,r-1]的答案 假设a[r]=x,要分两种情况讨论: 1)x+x!=M , 答案是 ans-c[M-x] 2)x+x==M,答案是 ans-(c[M-x]-1) 同理可以O(1)得到[l+1,r]的答案
  1. void erase(int x){
  2.     x=a[x];
  3.     ans-=c[M-x]-(x+x==M);
  4.     --c[x];
  5. }
现在知道[p,q]的答案,现在求[l,r]的答案 考虑右端点: 1)如果q<r,把a[q+1],a[q+2]…a[r]插入 2)如果q>r,把a[r+1],a[r+2]…a[q]删除 时间复杂度是|q-r| 考虑左端点: 1)如果p<l,把a[p],a[p+1]…a[l]删除 2)如果p>l,把a[l+1],a[l+2]…a[p]插入 时间复杂度是|p-l| 这个过程时间复杂度就是|p-l|+|q-r|
  1. while (q<r) insert(++q);
  2. while (q>r) erase(q--);
  3. while (p<l) erase(p++);
  4. while (p>l) insert(--p);
1)读入所有的询问,并记下是第几个询问 2)把N个数分成sqrt(N)块,算出每个询问的左端点在哪个块 pos=l/sqrt(N) 3)把询问以pos为第一关键字,r为第二关键字排序 4)按新的顺序求出所有询问的答案
  1. struct Query{
  2.     int id,l,r,pos;
  3.     bool operator<(const Query &t)const{
  4.         return pos!=t.pos?pos<t.pos:r<t.r; 
  5.     }
  6. };
  7. Query b[21000];
  8. sort(b+1,b+Q+1);  //  把b[1],b[2]...b[Q]排序
剩余代码:
  1. int main(){
  2.     int _;
  3.     scanf("%d",&_);
  4.     while (_--){
  5.         scanf("%d%d",&N,&M);
  6.         int i;
  7.         for (i=1;i<=N;i++) scanf("%d",&a[i]);
  8.         scanf("%d",&Q);
  9.         for (i=1;i<=Q;i++){
  10.             b[i].id=i;
  11.             scanf("%d%d",&b[i].l,&b[i].r);
  12.             b[i].pos=b[i].l/sqrt(N);
  13.         }
  14.         sort(b+1,b+Q+1);
  15.         memset(c,0,sizeof(c));
  16.         ans=0;
  17.         int p=1,q=1; insert(1);
  18.         for (i=1;i<=Q;i++){
  19.             int l=b[i].l,r=b[i].r;
  20.             while (q<r) insert(++q);
  21.             while (q>r) erase(q--);
  22.             while (p<l) erase(p++);
  23.             while (p>l) insert(--p);
  24.             t[b[i].id]=ans;
  25.         }
  26.         for (i=1;i<=Q;i++) printf("%I64d\n",t[i]);
  27.     }
  28. }
这个算法时间复杂度是O(N^1.5) 为什么呢? 1)对于那些左端点属于同一个块的询问 i)因为r是递增的,最差情况q从块的最左端加到N,O(N),一共N^0.5个块,所以这部分的复杂度是O(N^1.5)的 ii)p一次询问最多变化N^0.5,所以这部分的时间复杂度是O(Q*N^0.5) 2)从一个块跨越到另外一个块时 i)p最多变化2*N^0.5,最多跨越N^0.5,这部分复杂度是O(N) ii)最差情况下,q从N移动到最左端 N和Q范围一样,所以整个算法复杂度是O(N^1.5) 如果时间复杂度允许,可以用这个思想做很多区间询问的题目,但有个前提,整个过程中,不能有修改操作
转载保留版权:http://haipz.com/blog/i/857 - 海胖博客