全输出0

EDqwq @ 2021-02-03 21:55:53

by EDqwq @ 2021-02-03 21:56:06

#include<bits/stdc++.h>

#define int long long
#define mem(x) memset(x,0,sizeof(x))

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
    int num;
    int times;
}sum[1000010];

int n,m;
int a[1000010];
int l[1000010],r[1000010];
int num[1000010];
int block,len;

int query(int x,int y){
    int posl = num[x];
    int posr = num[y];
    node ans;
    ans.num = 0;
    ans.times = 2147483647;
    if(posl == posr){
        for(int i = x;i <= y;i ++){
            ans.num = 0;
            ans.times = 0;
            int now = 0;
            if(i == r[posl]){
                if(a[i] == a[i - 1])now ++;
                if(ans.times < now){
                    ans.times = now;
                    ans.num = a[i];
                    now = 0;
                }
                break;
            }
            if(a[i + 1] != a[i]){
                if(ans.times < now){
                    ans.times = now;
                    ans.num = a[i];
                    now = 0;
                }
            }
            else now ++;
        }
        return ans.num;
    }
    for(int i = x;i <= r[posl];i ++){
        int now = 0;
        if(i == r[posl]){
            if(a[i] == a[i - 1])now ++;
            if(ans.times < now){
                ans.times = now;
                ans.num = a[i];
                now = 0;
            }
            break;
        }
        if(a[i + 1] != a[i]){
            if(ans.times < now){
                ans.times = now;
                ans.num = a[i];
                now = 0;
            }
        }
        else now ++;
    }
    for(int i = num[x] + 1;i <= num[y] - 1;i ++){
        if(ans.times < sum[i].times){
            ans.times = sum[i].times;
            ans.num = sum[i].num;
        }
    }
    for(int i = l[posr];i <= y;i ++){
        int now = 0;
        if(i == y){
            if(a[i] == a[i - 1])now ++;
            if(ans.times < now){
                ans.times = now;
                ans.num = a[i];
                now = 0;
            }
            break;
        }
        if(a[i + 1] != a[i]){
            if(ans.times < now){
                ans.times = now;
                ans.num = a[i];
                now = 0;
            }
        }
        else now ++;
    }
    return ans.num;
}

signed main(){
    cin>>n>>m;
    block = sqrt(n);
    len = ceil(n * 1.0 / block);
    for(int i = 1;i <= n;i ++){
        a[i] = read();
        num[i] = (i - 1) / block + 1;
    }
    for(int i = 1;i <= len;i ++)sort(a + l[i],a + r[i] + 1);
    for(int i = 1;i <= len;i ++){
        l[i] = (i - 1) * block + 1;
        r[i] = i * block;
        int now = 0;
        for(int j = l[i];j <= r[i];j ++){
            if(j == r[i]){
                if(a[j] == a[j - 1])now ++;
                if(sum[i].times < now){
                    sum[i].times = now;
                    sum[i].num = a[j];
                    now = 0;
                }
                break;
            }
            if(a[j + 1] != a[j]){
                if(sum[i].times < now){
                    sum[i].times = now;
                    sum[i].num = a[j];
                    now = 0;
                }
            }
            else now ++;
        }
    }
    for(int i = 1;i <= m;i ++){
        int x,y;
        x = read(),y = read();
        cout<<query(x,y)<<endl;
    }
    return 0;
}

by DWT8125 @ 2021-02-03 22:04:15

Orz%%%

by 梦游的小雪球 @ 2021-02-03 22:06:50

@AC_chenpeizhe20 wyy回复会被鹿喷的

by Lwerecha @ 2021-02-03 22:21:38

@梦游的小雪球 两个不看问题水贴的...

by 梦游的小雪球 @ 2021-02-03 22:22:56

@Lwerecha 我是看到鹿才进来的

by Lwerecha @ 2021-02-03 22:28:52

@梦游的小雪球 [擦汗]跟某皮一样是水社区的..

by xtracer @ 2021-02-04 07:36:29

@林深时x见鹿 要不您试一下用暴力模拟？

by _5011_ @ 2021-02-04 08:27:40

@xtracer 你可能需要比较奇特的常数才能通过

by EDqwq @ 2021-02-04 08:28:44

@xtracer 你可能需要一个跟你一样不看数据范围的出数据人才能通过

by _5011_ @ 2021-02-04 08:29:37

等下，O(nm)=O(2e9) 2s也不是完全没有可能跑过/fad