程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Light OJ 1339 Strongest Community(分塊暴力）

Light OJ 1339 Strongest Community(分塊暴力）

編輯：關於C++

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.rpos[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;ir) Sub(R--);
            while(Rl) Add(--L);
            while(L