程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3809 -- 莫隊+分塊

bzoj3809 -- 莫隊+分塊

編輯:關於C++

bzoj3809 -- 莫隊+分塊。本站提示廣大學習愛好者:(bzoj3809 -- 莫隊+分塊)文章只能為提供參考,不一定能成為您想要的結果。以下是bzoj3809 -- 莫隊+分塊正文


題目大意:

給出一個序列和m個詢問,每個詢問求[l,r]中權值∈[a,b]的權值的種類數。

由於詢問是離線的,考慮莫隊。顯然可以用修改和查詢為O(log2n)的樹狀數組維護權值種類數,但這種做法的總時間復雜度是O(n*sqrt(n)*log2m),可能會TLE。

注意到總共有O(m)個查詢、O(n*sqrt(n))個修改,所以可以使用O(sqrt(n))查詢、O(1)修改的分塊。總時間復雜度為O(m*sqrt(n)+n*sqrt(n))

代碼:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 inline char nc(){
 8     static char buf[100000],*p1=buf,*p2=buf;
 9     if(p1==p2){
10         p2=(p1=buf)+fread(buf,1,100000,stdin);
11         if(p1==p2)return EOF;
12     }
13     return *p1++;
14 }
15 inline void Read(int& x){
16     char c=nc();
17     for(;c<'0'||c>'9';c=nc());
18     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
19 }
20 #define N 100010
21 #define M 1000010
22 #define lowbit(x) x&-x
23 struct Node{
24     int l,r,a,b,F;
25 }A[M];
26 int i,j,l,r,k,n,m,c[N],a[N],S,Ans[M],Ma,Sum[350],Cnt[N],b[N];
27 inline bool Cmp(Node x,Node y){
28     return b[x.l]<b[y.l]||(b[x.l]==b[y.l]&&x.r<y.r);
29 }
30 inline void U(int x){
31     Cnt[x]++;if(Cnt[x]==1)Sum[b[x]]++;
32 }
33 inline void D(int x){
34     Cnt[x]--;if(Cnt[x]==0)Sum[b[x]]--;
35 }
36 inline int Query(int x,int y){
37     int Ans=0;
38     if(b[y]-b[x]<=1){
39         for(;x<=y;x++)Ans+=(Cnt[x]?1:0);
40         return Ans;
41     }
42     for(int i=b[x]+1;i<b[y];i++)Ans+=Sum[i];
43     for(int i=x;b[i]==b[x];i++)Ans+=(Cnt[i]?1:0);
44     for(int i=y;b[i]==b[y];i--)Ans+=(Cnt[i]?1:0);
45     return Ans;
46 }
47 int s[20];
48 int Len;
49 inline void Print(int x){
50     if(x==0){putchar(48);putchar('\n');return;}
51     for(Len=0;x;x/=10)s[++Len]=x%10;
52     for(;Len;)putchar(s[Len--]+48);
53     putchar('\n');
54 }
55 int main()
56 {
57     Read(n);Read(m);
58     S=sqrt((double)n);
59     for(i=1;i<=n;i++)b[i]=(i-1)/S+1;
60     for(i=1;i<=n;i++){
61         Read(a[i]);
62         if(a[i]>Ma)Ma=a[i];
63     }
64     for(i=1;i<=m;i++){
65         Read(A[i].l);Read(A[i].r);Read(A[i].a);Read(A[i].b);
66         A[i].F=i;
67     }
68     sort(A+1,A+m+1,Cmp);
69     for(i=1,l=1,r=0;i<=m;i++){
70         while(A[i].r>r)U(a[++r]);
71         while(A[i].l>l)D(a[l++]);
72         while(A[i].r<r)D(a[r--]);
73         while(A[i].l<l)U(a[--l]);
74         Ans[A[i].F]=Query(A[i].a,A[i].b);
75     }
76     for(i=1;i<=m;i++)Print(Ans[i]);
77 } 
bzoj3809

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved