TOP

Light OJ 1339 Strongest Community(分块暴力）

2015-11-21 00:54:21 来源: 作者: 【大中小】浏览:1次

Tags：Light 1339 Strongest Community 分块暴力

In a strange city, houses are built in a straight line one after another. There are several communities in the city. Each community consists of some consecutivehouses such that every house belongs to exactly one community. The houses are numbered from 1 to n, and the communities are numbered from 1 to c.

Now some inspectors want to find the strongest community considering all houses from i to j. A community is strongest if maximum houses in the range belong to this community. So, there can be more than one strongest community in the range. So, they want to know the number of houses that belong to the strongest community. That's why they are seeking your help.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing three integers n (1 ≤ n ≤ 10⁵), c (1 ≤ c ≤ n) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers (each between 1 and c) denoting the communities the houses belong to. You can assume that the input follows the restrictions given above, and there are exactly c communities.

Each of the next q lines contains two integers i and j (1 ≤ i ≤ j ≤ n) denoting that the inspectors are asking for the result considering houses from i to j(inclusive).

Output

For each case, print the case number in a single line. Each of the next q lines should contain the number of houses that belong to the strongest community considering houses from i to j. The result should be listed in the same order as they are given in input.

Sample Input

Output for Sample Input

10 3 4

1 1 1 3 3 3 3 2 2 2

1 5

1 6

1 7

7 9

3 3 1

3 2 1

1 1

Case 1:

Case 2:

Note

Dataset is huge, use faster

题意：询问区间出现次数最多的数字出现次数

分析：线段树不会做，分块暴力吧，我们统计区间中数子出现次数

此时要统计两个信息：Add操作：增加一个数字会使出现频率变化，相应要修改最值

Sub操作：删除一个数字，如果删除数字后还有其他数达到相同水平，才改变最值

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) const int INF=0x3f3f3f3f; typedef long long LL; const int maxn=1e5+100; int pos[maxn],a[maxn]; int h[maxn],num[maxn]; int ans[maxn]; struct node{ int l,r; int id; }q[maxn]; int t,n,c,m; int sum; int cmp(node l1,node l2) { if(pos[l1.l]==pos[l2.l]) return l1.r
             
              pos[l2.l]; } void Add(int x) { int val=a[x]; h[num[val]]--; num[val]++; h[num[val]]++; if(num[val]>sum) sum=num[val]; } void Sub(int x) { int val=a[x]; h[num[val]]--; num[val]--; h[num[val]]++; if(sum==num[val]+1&&!h[num[val]+1]) sum=num[val]; } int main() { int x,y; int cas=1; scanf(%d,&t); while(t--) { scanf(%d%d%d,&n,&c,&m); CLEAR(h,0); CLEAR(num,0); int block=sqrt(n*1.0+0.5); REPF(i,1,n) { scanf(%d,&a[i]); pos[i]=(i-1)/block+1; } REP(i,m) { scanf(%d%d,&x,&y); q[i].l=x;q[i].r=y; q[i].id=i; } sort(q,q+m,cmp); sum=0;int L=1,R=0; printf(Case %d: ,cas++); for(int i=0;i
              
               r) Sub(R--); while(R
               
                l) Add(--L); while(L
                
                 ?
                 ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：BZOJ 题目2002: [Hnoi2010]Bounce..	下一篇：C++的struct和union

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: