萌新刚学 OI，求助 TLE 95pts 的蒲公英

SIXIANG32 @ 2022-03-20 21:09:23

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define MAXN 110000
#define QWQ cout << "qwq" << endl;
using namespace std;
int n, m, cnt;
int a[MAXN + 10], qaq[MAXN + 10];
int pl[MAXN + 10], pr[MAXN + 10], cl[MAXN + 10], len;
int c[MAXN + 10];
int f[1000 + 10][1000 + 10][2];
vector <int> vec[MAXN + 10];
int big, gib;
int finding(int l, int r, int x) {
    return upper_bound(vec[x].begin(), vec[x].end(), r) - lower_bound(vec[x].begin(), vec[x].end(), l);
}
void Three_Flower() {
    for(int p = 1; p <= n; p++) qaq[p] = a[p];
    sort(qaq + 1, qaq + n + 1);
    cnt = unique(qaq + 1, qaq + n + 1) - qaq - 1;
    for(int p = 1; p <= n; p++)
        a[p] = lower_bound(qaq + 1, qaq + cnt + 1, a[p]) - qaq;
}
void qwq(int l, int r, int num) {
    int cnt = finding(l, r, num);
    if(cnt > big || (cnt == big && num < gib)) {
        big = cnt;
        gib = num;
    }
}
int solve(int l, int r) {
    int L = cl[l], R = cl[r];
    int x = 0, y = 0;
    if(L + 1 <= R - 1) x = L + 1, y = R - 1;
    big = f[x][y][0], gib = f[x][y][1];
    if(L == R)
        for(int p = l; p <= r; p++) qwq(l, r, a[p]);
    else {
        for(int p = l; p <= pr[L]; p++) qwq(l, r, a[p]);
        for(int p = pl[R]; p <= r; p++) qwq(l, r, a[p]);
    }
    return qaq[gib];
}
void block() {
    len = sqrt(log(n) / log(2) * n);
    for(int p = 1; p <= ceil(n * 1.0 / len); p++) {
        pl[p] = (p - 1)* len + 1;
        pr[p] = p * len;
    }
    for(int p = 1; p <= n; p++)
        cl[p] = (p - 1) / len + 1;
    for(int p = 1; p <= ceil(n * 1.0 / len); p++)
        for(int i = p; i <= ceil(n * 1.0 / len); i++) {
            memset(c, 0, sizeof(c));
            for(int j = pl[p]; j <= pr[i]; j++) c[a[j]]++;
            for(int j = 1; j <= cnt; j++)
                if(c[j] > f[p][i][0] || (c[j] == f[p][i][0] && j < f[p][i][1]))
                    f[p][i][0] = c[j], f[p][i][1] = j;
        }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int p = 1; p <= n; p++) scanf("%d", &a[p]);
    Three_Flower();
    for(int p = 1; p <= n; p++) vec[a[p]].push_back(p);
    block();
    int last = 0;
    while(m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        x = (x + last - 1) % n + 1, y = (y + last - 1) % n + 1;
        if(x > y) swap(x, y);
        last = solve(x, y);
        printf("%d\n", last);
    }
}

by wkywkywky @ 2022-03-20 21:11:01

@Little_Sealx 快读

by lzqy_ @ 2022-03-20 21:11:08

@Little_Sealx 开个快读就过了吧

by SIXIANG32 @ 2022-03-20 21:13:16

@lzqy_ 寄吧，我之前 n^{5/3} 做法 cin+cout 就草爆了然后还挺快，没想到啊/fad
我试试/qq

by SIXIANG32 @ 2022-03-20 21:15:52

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define MAXN 50000
#define QWQ cout << "qwq" << endl;
using namespace std;
int n, m, cnt;
int a[MAXN + 10], qaq[MAXN + 10];
int pl[MAXN + 10], pr[MAXN + 10], cl[MAXN + 10], len;
int c[MAXN + 10];
int f[900 + 10][900 + 10][2];
vector <int> vec[MAXN + 10];
inline int read()
{
    int ans=0;
    char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    return ans;
}
inline void write(int x)
{
    char f[200];
    int tmp=x>0?x:-x,cnt=0;
    if(x<0)putchar('-');
    while(tmp>0)f[cnt++]=tmp%10+'0',tmp/=10;
    while(cnt>0)putchar(f[--cnt]);
    putchar('\n');
}
int big, gib;
int finding(int l, int r, int x) {
    return upper_bound(vec[x].begin(), vec[x].end(), r) - lower_bound(vec[x].begin(), vec[x].end(), l);
}
void Three_Flower() {
    for(int p = 1; p <= n; p++) qaq[p] = a[p];
    sort(qaq + 1, qaq + n + 1);
    cnt = unique(qaq + 1, qaq + n + 1) - qaq - 1;
    for(int p = 1; p <= n; p++)
        a[p] = lower_bound(qaq + 1, qaq + cnt + 1, a[p]) - qaq;
}
void qwq(int l, int r, int num) {
    int cnt = finding(l, r, num);
    if(cnt > big || (cnt == big && num < gib)) {
        big = cnt;
        gib = num;
    }
}
int solve(int l, int r) {
    int L = cl[l], R = cl[r];
    int x = 0, y = 0;
    if(L + 1 <= R - 1) x = L + 1, y = R - 1;
    big = f[x][y][0], gib = f[x][y][1];
    if(L == R)
        for(int p = l; p <= r; p++) qwq(l, r, a[p]);
    else {
        for(int p = l; p <= pr[L]; p++) qwq(l, r, a[p]);
        for(int p = pl[R]; p <= r; p++) qwq(l, r, a[p]);
    }
    return qaq[gib];
}
void block() {
    len = sqrt(log(n) / log(2) * n);
    for(int p = 1; p <= ceil(n * 1.0 / len); p++) {
        pl[p] = (p - 1)* len + 1;
        pr[p] = p * len;
    }
    for(int p = 1; p <= n; p++)
        cl[p] = (p - 1) / len + 1;
    for(int p = 1; p <= ceil(n * 1.0 / len); p++)
        for(int i = p; i <= ceil(n * 1.0 / len); i++) {
            memset(c, 0, sizeof(c));
            for(int j = pl[p]; j <= pr[i]; j++) c[a[j]]++;
            for(int j = 1; j <= cnt; j++)
                if(c[j] > f[p][i][0] || (c[j] == f[p][i][0] && j < f[p][i][1]))
                    f[p][i][0] = c[j], f[p][i][1] = j;
        }
}
int main() {
    n = read(), m = read();
    for(int p = 1; p <= n; p++) a[p] = read();
    Three_Flower();
    for(int p = 1; p <= n; p++) vec[a[p]].push_back(p);
    block();
    int last = 0;
    while(m--) {
        int x, y;
        x = read(), y = read();
        x = (x + last - 1) % n + 1, y = (y + last - 1) % n + 1;
        if(x > y) swap(x, y);
        last = solve(x, y);
        write(last);
    }
}

还是不行/wq

by Nevergonna_CCF @ 2022-03-20 21:26:31

用这个快读快输

@Little_Sealx

by 王熙文 @ 2022-03-20 21:26:36

块长设 200 瞬间过

this

by Nevergonna_CCF @ 2022-03-20 21:27:21

#define reg register
struct control{
    int ct,val;
    control(int Ct,int Val=-1):ct(Ct),val(Val){}
    inline control operator()(int Val){
        return control(ct,Val);
    }
}_endl(0),_prs(1),_setprecision(2);
struct FastIO{
    #define IOSIZE 1000000
    char in[IOSIZE],*p,*pp,out[IOSIZE],*q,*qq,ch[20],*t,b,K,prs;
    FastIO():p(in),pp(in),q(out),qq(out+IOSIZE),t(ch),b(1),K(6){}
    ~FastIO(){fwrite(out,1,q-out,stdout);}
    inline char getch(){
        return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?b=0,EOF:*p++;
    }
    inline void putch(char x){
        q==qq&&(fwrite(out,1,q-out,stdout),q=out),*q++=x;
    }
    inline void puts(const char str[]){fwrite(out,1,q-out,stdout),fwrite(str,1,strlen(str),stdout),q=out;}
    inline void getline(string& s){
        s="";
        for(reg char ch;(ch=getch())!='\n'&&b;)s+=ch;
    }
    #define indef(T) inline FastIO& operator>>(T& x){\
        x=0;reg char f=0,ch;\
        while(!isdigit(ch=getch())&&b)f|=ch=='-';\
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getch();\
        return x=f?-x:x,*this;\
    }
    indef(int)
    indef(long long)
    inline FastIO& operator>>(char& ch){return ch=getch(),*this;}
    inline FastIO& operator>>(string& s){
        s="";reg char ch;
        while(isspace(ch=getch())&&b);
        while(!isspace(ch)&&b)s+=ch,ch=getch();
        return *this;
    }
    inline FastIO& operator>>(double& x){
        x=0;reg char f=0,ch;
        double d=0.1;
        while(!isdigit(ch=getch())&&b)f|=(ch=='-');
        while(isdigit(ch))x=x*10+(ch^48),ch=getch();
        if(ch=='.')while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1;
        return x=f?-x:x,*this;
    }
    #define outdef(_T) inline FastIO& operator<<(_T x){\
        !x&&(putch('0'),0),x<0&&(putch('-'),x=-x);\
        while(x)*t++=x%10+48,x/=10;\
        while(t!=ch)*q++=*--t;\
        return *this;\
    }
    outdef(int)
    outdef(long long)
    inline FastIO& operator<<(char ch){return putch(ch),*this;}
    inline FastIO& operator<<(const char str[]){return puts(str),*this;}
    inline FastIO& operator<<(const string& s){return puts(s.c_str()),*this;}
    inline FastIO& operator<<(double x){
        reg int k=0;
        this->operator<<(int(x));
        putch('.');
        x-=int(x);
        prs&&(x+=5*pow(10,-K-1));
        while(k<K)putch(int(x*=10)^48),x-=int(x),++k;
        return *this;
    }
    inline FastIO& operator<<(const control& cl){
        switch(cl.ct){
            case 0:putch('\n');break;
            case 1:prs=cl.val;break;
            case 2:K=cl.val;break;
        }
    }
    inline operator bool(){return b;}
}io;
#undef reg
//用法：输入:io>>x;输出:io<<x;

by SIXIANG32 @ 2022-03-20 21:28:45

@王熙文 谢谢 wxw！/qq

by wkywkywky @ 2022-03-20 21:29:54

@Little_Sealx 时间复杂度是假的吧，这个memset 不对吧

by SIXIANG32 @ 2022-03-20 21:31:57

@wkywkywky 寄吧，好像假了，蟹蟹！♪(･ω･)ﾉ