P7882 [Ynoi2006] rsrams 题解

· · 题解

大常数选手 + 大常数做法 = 最劣解，从 15.50 一直卡到 21.50 才过

若一个区间有贡献，那么该区间众数出现次数大于区间长度的一半。考虑根号分治，设阈值为 B。

取 B=n^{\frac{3}{4}} 可以做到 O(n^{\frac{4}{7}})，可以通过 n,m\le10^{5} 和 a_{i}\le2。以上是赛时的垃圾做法

发现所有数出现的总次数为 n，每个数对长为 n 的序列做莫队是非常亏的。考虑类似虚树的思想：对该数出现的所有位置，标记该位置及其左右第一个未标记的位置，把这些位置拿出来形成一个虚序列，设长为 n_{i}，调节莫队块长可以做到 O(m+n_{i}\sqrt{m})。由于 \sum n_{i}=O(n)，总复杂度 O(\frac{nm}{B}+n\sqrt{m})

设 n,m 同阶，设 B=\sqrt{n} 即可得到 O(n\sqrt{n}) 做法
注意上面所分析的阈值/块长忽略了常数，xjb 调一调能得到更好的表现

代码非常丑陋

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
#define For(i,x,y,...) for(int i=x,##__VA_ARGS__;i<=(y);++i)
#define rFor(i,x,y,...) for(int i=x,##__VA_ARGS__;i>=(y);--i)
#define Rep(i,x,y,...) for(int i=x,##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
#define all(a) begin(a),end(a)
#define fi first
#define se second
typedef long long LL; typedef vector<int> Vi;
auto ckmax=[](auto &x,auto y) { return x<y ? x=y,true : false; };
auto ckmin=[](auto &x,auto y) { return y<x ? x=y,true : false; };
sfmt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) { return uniform_int_distribution<>(l,r)(mt); }
#define endl '\n'
namespace IO { const int L = 1<<25; char a[L],*l=a,*r=a,b[L],*p=b;
auto gc=[]() { if(l==r)r=(l=a)+fread(a,1,L,stdin);return l==r?EOF:*l++; };
auto pc=[](char x) { if(p-b==L)fwrite(b,1,L,stdout),p=b;*p++=x; };
struct IO {
    ~IO() { fwrite(b,1,p-b,stdout); }
    template<typename T>IO& operator >> (T &x) {
        x=0;bool f=1;char c;while(!isdigit(c=gc()))f&=c!='-';
        if(f)do x=x*10+c-48;while(isdigit(c=gc()));
        else do x=x*10-c+48;while(isdigit(c=gc()));
        return *this;
    }
    IO& operator << (char x) { pc(x); return *this; }
    IO& operator << (LL x) {
        static char s[22];
        if(!x)pc(48);
        else{char *t=s;do *t++=x%10;while(x/=10);while(s!=t)pc(*--t|48);}
        return *this;
    }
} io; } using IO::io;
template<typename T=int>T read() { T x; io>>x; return x; }

const int N = 1e6+5;
int n,q,lim,a[N],ql[N],qr[N],tot[N],siz[N],sa[N];
LL ans[N];

namespace part1 {
int mx,cnt[N];
Vi q[N];
struct Block {
    static const int B = 1e3, BN = N/B+5;
    int in[N],le[BN],a[N]; LL tot,s[BN];
    void init() {
        For(i,1,n) in[i] = (i-1)/B+1;
        le[1] = 1; For(i,2,in[n]) le[i] = le[i-1]+B;
    }
    void add(int i,int x) { a[i] += x, s[in[i]] += x, tot += x; }
    LL sum(int r) {
        int rr = in[r]; LL res = 0;
        Rep(i,1,rr) res += s[i];
        For(i,le[rr],r) res += a[i];
        return res;
    }
} blk;
void main() {
    blk.init();
    For(i,1,::q) q[qr[i]].pb(i);
    For(r,1,n) {
        int ll = max(1,r-2*lim+1), l = r;
        for(; l >= ll; --l) {
            if( tot[a[l]] <= lim ) {
                cnt[a[l]] += 2;
                if( cnt[a[l]] > cnt[mx] ) mx = a[l];
            }
            if( cnt[mx] > r-l+1 ) blk.add(l,mx);
            else if( cnt[mx]+2*(l-ll) <= r-ll+1 ) { --l; break; }
        }
        mx = 0; while( l < r ) cnt[a[++l]] -= 2;
        for(int i : q[r]) ans[i] += blk.tot-blk.sum(ql[i]-1);
    }
    cerr<<"part1: "<<clock()/1e6<<"s\n";
}
}

namespace part2 {
int m,q,p[N],w[N],le[N],ri[N],in[N],sa[N],ql[N],qr[N],id[N],ds[N*2];
bitset<N> vis;
void _sort() {
    static int buc[N];
    For(i,1,m, b = max(2*m/sqrt(q),1.)) in[i] = (i-1)/b+1;
    memset(buc+1,0,sizeof(int)*m);
    For(i,1,q) ++buc[in[ql[i]]]; For(i,1,m) buc[i] += buc[i-1];
    rFor(i,q,1) id[buc[in[ql[i]]]--] = i;
//  Rep(i,1,q)
//      if( in[ql[id[i]]] == in[ql[id[i+1]]] ) assert(qr[id[i]]<=qr[id[i+1]]);
//      else assert(in[ql[id[i]]]<in[ql[id[i+1]]]);
    For(i,1,q) if( !(in[ql[id[i]]] & 1) ) {
        int j = i; while( j < q && in[ql[id[j]]] == in[ql[id[j+1]]] ) ++j;
        reverse(id+i,id+j+1), i = j;
    }
}
void mo(int x) {
    m = q = 0, vis.reset();
    For(i,1,n, j = 0)
        if( a[i] == x ) vis[i] = 1, ++j;
        else if( j ) vis[i] = 1, --j;
    rFor(i,n,1, j = 0)
        if( a[i] == x ) ++j;
        else if( j ) vis[i] = 1, --j;
    For(i,1,n) if( vis[i] ) p[++m] = i;
//  For(i,1,m) assert(abs(w[i]-w[i-1])==1);
    w[0] = m; For(i,1,m) w[i] = a[p[i]]==x ? w[i-1]+1 : w[i-1]-1;
    Rep(i,1,m) {
        le[p[i]] = ri[p[i]] = i;
        Rep(j,p[i]+1,p[i+1]) le[j] = i, ri[j] = i+1;
    } le[p[m]] = ri[p[m]] = m;
    For(i,1,::q) {
        int l = ::ql[::sa[i]], r = ::qr[::sa[i]];
        if( r < p[1] || p[m] < l ) continue;
        sa[++q] = ::sa[i], ql[q] = ri[max(l,p[1])], qr[q] = le[min(r,p[m])];
        if( ql[q] > qr[q] ) --q;
    }
    _sort();
    int T=0; LL now = 0, pre = 0, suf = 0;
    memset(ds+1,0,sizeof(int)*2*m);
    For(i,1,q, l = 1, r = 0, lp = m, rp = m) {
        int j = id[i];
//      T += abs(r-qr[j])+abs(l-ql[j]);
        while( r < qr[j] )
            rp<w[++r] ? pre+=ds[rp++] : pre-=ds[--rp],
            now += (w[l-1]<w[r])+pre, ++ds[rp], suf += lp<rp;
        while( l > ql[j] )
            ++ds[lp], pre += lp<rp,
            lp>w[(--l)-1] ? suf+=ds[lp--] : suf-=ds[++lp], now += suf;
        while( r > qr[j] )
            now -= (w[l-1]<w[r])+pre, --ds[rp], suf -= lp<rp,
            rp<w[--r] ? pre+=ds[rp++] : pre-=ds[--rp];
        while( l < ql[j] )
            now -= suf, lp>w[l++] ? suf+=ds[lp--] : suf-=ds[++lp],
            --ds[lp], pre -= lp<rp;
//      assert(lp==w[l-1]), assert(rp==w[r]),
        ans[sa[j]] += x * now;
    }
//  cerr<<T<<' '<<int(m*sqrt(q))<<endl;
}
void main() {
    int T=0;
    For(i,1,n) if( tot[i] > lim ) ++T, mo(i);
    cerr<<"part2: "<<T<<endl;
}
}

signed main() {
    io>>n>>q; For(i,1,n) ++tot[a[i]=read()];
    For(i,1,n) ++siz[tot[i]]; For(i,1,q) io>>ql[i]>>qr[i];
    for(lim = 1000; !siz[lim]; --lim);
    cerr<<"lim = "<<lim<<endl;
    iota(sa+1,sa+q+1,1), sort(sa+1,sa+q+1,[](int x,int y){return qr[x]<qr[y];});
    part1::main(), part2::main();
    For(i,1,q) io<<ans[i]<<endl;
    return 0;
}

upd：莫队奇偶优化那里边界挂了