救命！救命！救命！

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

#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 Rye_Catcher @ 2018-08-15 21:26:19

第一次写分块就先不要头铁做这道题吧。。。

by Randyhoads @ 2018-08-15 21:27:20

@An_Account 听说这道题用主席树可以水过，我反正是放弃了，你可以不写分块，去写写主席树（心理阴暗+滑稽）

by Randyhoads @ 2018-08-15 21:28:15

@An_Account 改一改交道LOJ 数列分块入门9，可以下数据调试

by An_Account @ 2018-08-15 21:38:31

@WLZS 用主席树维护...众数？

by Randyhoads @ 2018-08-15 21:39:49

@An_Account 我反正是这样做的，但是只能水到95分

by An_Account @ 2018-08-15 21:45:59

区间众数这种问题线段树维护不了吧...

我又交了hzwer上的标程,RE 25分...

by An_Account @ 2018-08-15 21:47:22

@WLZS 有一个人叫做ZJK

by Randyhoads @ 2018-08-15 21:50:38

@An_Account 1.值域线段树可以维护区间众数 2.ZJK AK！

by An_Account @ 2018-08-15 21:52:59

ZJK:我没实名好难受.jpg

by Randyhoads @ 2018-08-15 21:53:14

@An_Account 这是我的代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)

using namespace std;

inline char nc()
{
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}

inline int read()
{
    char ch;
    int fl=1;
    int x=0;
    do{
      ch= nc();
      if(ch=='-')
        fl=-1;
    }while(ch<'0'||ch>'9');
    do{
        x=(x<<3)+(x<<1)+ch-'0';
        ch=nc();
    }while(ch>='0'&&ch<='9');
    return x*fl;
}

const int MAXN = 40000+10;

struct p_tree
{
    int sum;
    int lcc;
    int rcc;    
} ;

p_tree t[MAXN*20];

int root[MAXN],cnt=0;

struct node
{
    int val;
    int id;
    friend bool operator < (node a1,node a2)
    {
        return a1.val<a2.val;   
    } 
};

node a[MAXN];

int c[MAXN];

int zsi,zsz;

bool bz; 

int ck;

void update(int& rt,int x,int k,int l,int r)
{
    t[++cnt]=t[rt];
    rt = cnt;
    t[rt].sum+=k;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) update(t[rt].lcc,x,k,l,mid);
    else update(t[rt].rcc,x,k,mid+1,r);
}

void query(int l,int r,int x,int y)
{
    if(bz) return;
    if(x==y)
    {
        if(zsz<t[r].sum-t[l].sum)
        {
            zsz=t[r].sum-t[l].sum;
            zsi=x;
        }
        if(zsz>(ck)/2) 
        {
            bz = true;
        }
        return;
    }
    else
    {
        if(zsz<t[t[r].lcc].sum-t[t[l].lcc].sum)
        {
            query(t[l].lcc,t[r].lcc,x,(x+y)>>1);    
        }
        if(zsz<t[t[r].rcc].sum-t[t[l].rcc].sum)
        {
            query(t[l].rcc,t[r].rcc,((x+y)>>1)+1,y);    
        } 
    } 
}

int n,q;

int rankk[MAXN];

int main()
{
    n=read(),q=read();
    for(register int i=1;i<=n;i++) a[i].val=read(),a[i].id=i;;
    root[0]=0;
    t[0].sum=t[0].lcc=t[0].rcc=0;
    sort(a+1,a+n+1);
    int top=0;
    for(register int i=1;i<=n;i++)
    {
        if(a[i].val!=a[i-1].val) top++;
        c[a[i].id]=top;
        rankk[top]=a[i].val;
    }
    for(register int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        update(root[i],c[i],1,1,40000);
    }
    zsi=0,zsz=0;
    for(register int i=1;i<=q;i++)
    {
        bz = false;
        int l0=read(),r0=read();
        int u=(l0+rankk[zsi]-1)%n+1,v=(r0+rankk[zsi]-1)%n+1;
        if(u>v) swap(u,v);
        ck = v-u+1;
        zsi = 0,zsz = 0;
        query(root[u-1],root[v],1,40000);
        printf("%d\n",rankk[zsi]);
    }
}