救命!救命!救命!

P4168 [Violet] 蒲公英

An_Account @ 2018-08-15 21:19:37

第一次写分块,但是一直RE,不知道为什么。而且开O_2,调数组大小,改分块个数全都试过,但是还是RE,求助DALAO!!!!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define N 40010
#define B 810
int len,f[B][B],at[N],cnt[N],n,m,v[N],val[N];
vector<int> id[N];
void pre(int x) {
    memset(cnt,0,sizeof(cnt));
    int mx=0,ans=0;
    for (int i=(x-1)*len+1;i<=n;i++) {
        cnt[v[i]]++;
        if (cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))
            ans=v[i],mx=cnt[v[i]];
        f[x][at[i]]=ans;
    }
}
int query(int l,int r,int x) {
    vector<int>::iterator start=lower_bound(id[x].begin(),id[x].end(),l);
    vector<int>::iterator end=upper_bound(id[x].begin(),id[x].end(),r);
    return end-start;
}
int query(int start,int end) {
    int ans=f[at[start]+1][at[end]-1],mx=query(start,end,ans);
    for (int i=start;i<=min(at[start]*len,end);i++) {
        int t=query(start,end,v[i]);
        if (t>mx||(t==mx&&val[v[i]]<val[ans])) ans=v[i],mx=t;
    }
    if (at[start]!=at[end]) 
        for (int i=(at[end]-1)*len+1;i<=end;i++) {
            int t=query(start,end,v[i]);
            if (t>mx||(t==mx&&val[v[i]]<val[ans])) ans=v[i],mx=t;
        }
    return val[ans];
}
map<int,int> H;int hcnt;
int main() {
    scanf("%d%d",&n,&m),len=sqrt(n*log2(n));
    for (int i=1;i<=n;i++) {
        scanf("%d",&v[i]),at[i]=(i-1)/len+1;
        if (!H[v[i]]) H[v[i]]=++hcnt,val[hcnt]=v[i];
        v[i]=H[v[i]],id[v[i]].push_back(i);
    }
    for (int i=1;i<=at[n];i++) pre(i);
    int lastans=0;
    for (int i=1;i<=m;i++) {
        int start,end;scanf("%d%d",&start,&end);
        start=(start+lastans-1)%n+1,end=(end+lastans-1)%n+1;
        if (start>end) swap(start,end);
        printf("%d\n",lastans=query(start,end));
    }
    return 0;
}

by Randyhoads @ 2018-08-15 21:54:07

其实本质上就是个暴力


by Randyhoads @ 2018-08-15 21:54:36

网上有人说主席树能过,但是我不知道怎么写,就写了一个类似暴力的东西


by An_Account @ 2018-08-15 21:55:39

@WLZS 这样一次查询最坏是O(n)的啊


by Randyhoads @ 2018-08-15 21:56:18

@An_Account 然后ZJK实名了


by An_Account @ 2018-08-15 21:57:41

@WLZS 他没实名啊(他刚刚还想给您发私信然后发现发不起)


by An_Account @ 2018-08-15 22:04:24

其实ZJK也在写这道题结果RE+WA了


by Randyhoads @ 2018-08-15 22:16:22

@An_Account orz ZJK


by An_Account @ 2018-08-16 07:45:14

我终于过了这道题

把原来的O(m\sqrt n\ log\ n)优化到了O(m\sqrt n)

谢谢大家的帮助


上一页 |