考场

没有一眼题

T1 想到先贪心地算出最大得分，任意构造出一种方案，不断调整以增大字典序。

T2 发现在 \(x_k\) 确定的情况下操作次数就是左右两边的逆序对数，\(x_i\) 互不相同时直接找到最大值，枚举它最终的位置，BIT 动态维护逆序对。若有相同则最大的 \(x_i\) 最终的位置没有交集，并集为 \(n\)，感觉非常对。

T3 没多想

T1 一开始以为每个位置只会换成一个它后面的更大的 \(a\)，那么就可以以 \(b\) 为下标，\(a\) 为值建线段树，在保证得分最大的情况下贪心的换，拍了拍开始调，然后就降智了。。。最后分 \(4\) 类，写两颗线段树，并且还是假的。加了个卡时，9.40 才丢开

直接写 T3 暴力，以为“彩灯能够覆盖的区间两两之间只有包含和不相交的关系”是对选出区间的要求（其实是给出区间的性质），于是只能 \(O(2^mm^2)\)

T2 没 rush 完，交了个过不了样例的程序

res

rk22 20+0+0

只有用来拍 T1 的暴力有分。。。

T3 全 T 了

rk1 yzf 20+100+45

rk3 ycx 20+30+45

rk6 ys 10+10+45

rk9 wcr 20+30+0

rk13 lrx 20+20+0

rk18 zjj 10+20+0

rk22 mtr 20+0+0

总结

我记得和 hkh 说过，考场写 DS 就要做好调不出来爆 \(0\) 的准备，今天就应验了。。。

在其他两道题一分没有的情况下肝一道题超过 2h 无论如何都是极其错误的决策

如果决定要莽数据结构，那就先把其他两题的暴力写完，至少不会死的太难看

对于正确性，我大部分都是靠感觉。有一句话是一个正确的算法每个细节都是值得推敲的，如果自己都含糊不清，想的是写出来再 gdb，那不是会浪费很多时间就是做法假了。开始敲之前想清楚每个细节，尝试 hack 一会或证明正确性，复杂的 DS/DP 在纸上列好。

sol

没时间写了。。。

T1

\(O(n\log^2n)\)

char buf[1<<24],*p1=buf,*p2=buf,pbuf[1<<24],*pp=pbuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
#define iocl() fwrite(pbuf,1,pp-pbuf,stdout),pp=pbuf,0
#define putchar(x) pp-pbuf==1<<22&&(iocl()),*pp++=x
int read(){
    int x=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    for(;isdigit(c);c=getchar())x=x*10+c-48;
    return x;
}
void write(int x) {
    static int s[11];int l=0;
    for(;x;x/=10)s[l++]=x%10;while(l)putchar(s[--l]|48);
    putchar(' ')
}

const int N = 2e5+5;
int n,b[N],a[N];

int ans,mn,mx,cnt[N],cntb[N];

int tn;
struct Node { int l,r,a,b,s; } t[N*8];
void up(int u) {
    int ls = u<<1, rs = ls|1;
    int s = min(t[ls].b,t[rs].a);
    t[u].s = t[ls].s + t[rs].s + s;
    t[u].a = t[ls].a + t[rs].a - s;
    t[u].b = t[ls].b + t[rs].b - s;
}
void build() {
    int n = max(*max_element(b+1,b+::n+1),mx);
    tn = 1 << int(log2(n+1)+2);
    For(i,1,n) t[tn+i].a = cnt[i], t[tn+i].b = cntb[i];
    rFor(i,tn-1,1) up(i);
}
void modify(int p,int x,int y) {
    t[ p+=tn ].a += x, t[p].b += y;
    while( p >>= 1 ) up(p);
}

signed main() {
    n=read();
    For(i,1,n) b[i]=read(), ++cntb[b[i]];
    For(i,1,n) a[i]=read(), ++cnt[a[i]];
    mn = *min_element(a+1,a+n+1), mx = *max_element(a+1,a+n+1);
    build();
    ans = t[1].s;
    For(i,1,n) {
        modify(b[i],0,-1);
        int l = max(mn,b[i]+1), r = mx;
        while( l < r ) {
            int mid = l+r+1>>1;
            modify(mid,-1,0);
            if( 1+t[1].s == ans ) l = mid;
            else r = mid-1;
            modify(mid,1,0);
        }
        modify(l,-1,0);
        if( l <= r && 1+t[1].s == ans ) --ans;
        else {
            modify(l,1,0);
            l = mn, r = min(mx,b[i]);
            while( l < r ) {
                int mid = l+r+1>>1;
                modify(mid,-1,0);
                if( t[1].s == ans ) l = mid;
                else r = mid-1;
                modify(mid,1,0);
            }
            modify(l,-1,0);
        }
        --cnt[l];
        while( mn <= mx && !cnt[mx] ) --mx;
        while( mn <= mx && !cnt[mn] ) ++mn;
        write(l);
    }
    return iocl();
}

还有线段树二分的 \(O(n\log n)\) 做法 by 沈子舜

#include<bits/stdc++.h>
using namespace std;
#define uu unsigned
#define scanf abc=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define forg(i,x) for(int i=fir[x];i;i=nxt[i])
int abc;
typedef pair<int,int>pii;
typedef long long ll;
typedef uu long long ull;
typedef vector<int>VI;
inline int rd(int l,int r){return rand()%(r-l+1)+l;}

const int mxn=1e5+3,S=mxn;
int n,a[mxn],b[mxn],px[mxn],ans[mxn];
int d[mxn],m,ind[mxn],M;
int grk(int x){return upper_bound(a+1,a+n+1,x)-a;}
bool cmp1(int x,int y){return b[x]<b[y];}
set<pii>st;
void wk1(){
    for(int i=1;i<=n;++i)px[i]=i;sort(px+1,px+n+1,cmp1);
    int p=0;
    while(m<n){
        int h=px[m+1];
        p=max(p+1,grk(b[h]));
        if(p<=n)d[++m]=h,ind[h]=m;
        else return;
    }
}
struct lks{
    int a[mxn];
    void del(int x){for(;x;x-=x&-x)--a[x];}
    void add(int x){for(;x;x-=x&-x)++a[x];}
    int ask(int x){++x;int r=0;for(;x<=S;x+=x&-x)r+=a[x];return r;}
}a1;
#define mid ((l+r)>>1)
struct sdx{
    int mn[mxn*4],tg[mxn*4];
    void bu(int x=1,int l=1,int r=M){
        if(l==r)return mn[x]=a1.ask(b[d[l]])-(m-l+1),void();        bu(x*2,l,mid),bu(x*2+1,mid+1,r),up(x);
    }
    void add(int lc,int rc,int v,int x=1,int l=1,int r=M){
        assert(lc<=rc);
        if(lc<=l&&r<=rc)return put(x,v);
        down(x);if(lc<=mid)add(lc,rc,v,x*2,l,mid);if(rc>mid)add(lc,rc,v,x*2+1,mid+1,r);
        up(x);
    }
    int ask(int k,int x=1,int l=1,int r=M){if(l==r)return mn[x];down(x);return k<=mid?ask(k,x*2,l,mid):ask(k,x*2+1,mid+1,r);}
    void down(int x){if(tg[x])put(x*2,tg[x]),put(x*2+1,tg[x]),tg[x]=0;}
    void put(int x,int v){mn[x]+=v,tg[x]+=v;}
    void inf(int k,int x=1,int l=1,int r=M){
        if(l==r)return mn[x]=1e9,void();
        down(x);
        if(k<=mid)inf(k,x*2,l,mid);else inf(k,x*2+1,mid+1,r);up(x);
    }
    void up(int x){mn[x]=min(mn[x*2],mn[x*2+1]);}
    int ask0(int x=1,int l=1,int r=M){
        assert(mn[x]>=0);
        if(l==r)return mn[x]==0?l:l+1;
        down(x);
        if(mn[x*2]>0)return ask0(x*2+1,mid+1,r);else return ask0(x*2,l,mid);
    }
}se;
#undef mid
bool chk1(int k){
    if(ind[k])return 1;
    return a1.ask(b[k]);
}
int lowr(int x){int l=0,r=m,md;while(l<r){md=(l+r+1)>>1;if(b[d[md]]<x)l=md;else r=md-1;}return l;}
int main(){
    scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",b+i);for(int i=1;i<=n;++i)scanf("%d",a+i);sort(a+1,a+n+1);
    wk1();for(int i=1;i<=n;++i)a1.add(a[i]);M=m;se.bu();for(int i=1;i<=n;++i)st.insert(pii(a[i],i));
    for(int t=1;t<=n;++t){
        if(m)assert(ind[d[m]]);
//        int mm=0;for(int i=1;i<=m;++i)mm+=ind[d[i]]!=0;    cout<<t<<"!\n";cout<<m<<' '<<mm<<endl;        for(int i=1,j=0;i<=m;++i)if(ind[d[i]])++j,printf("%d %d ",i,j),cout<<se.ask(i)<<' '<<endl,assert(se.ask(i)==a1.ask(b[d[i]])-(mm-j+1));
        if(!m){auto it=--st.end();int k=it->second;ans[t]=a[k],st.erase(pii(a[k],k));continue;}
        bool bb=chk1(t);
        if(bb){
            if(ind[t])se.add(ind[t],m,-1),se.inf(ind[t]),ind[t]=0;
            else{while(!ind[d[m]])--m;ind[d[m]]=0,--m;}
            while(m>0&&!ind[d[m]])--m;
            if(m)se.add(1,m,1);
        }
        int rr=m?se.ask0():2;
//        for(int i=1;i<rr&&i<=m;++i)assert(se.ask(i)>0);assert(rr>m||se.ask(rr)==0);
        rr=rr>m?2e5:b[d[rr]];
        if(!bb)rr=min(rr,b[t]);
        auto it=--st.lower_bound(pii(rr,1e9));
        int k=it->second;
        ans[t]=a[k],st.erase(pii(a[k],k)),a1.del(a[k]);
        int pp=lowr(ans[t]);
        if(pp)se.add(1,pp,-1);
    }
    for(int i=1;i<=n;++i)printf("%d ",ans[i]);puts("");
    return 0;
} T2

const int N = 1e5+5;
int n,b[N];

int a[N];
LL ans;

#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
struct Node{ int sum; PII mn; } t[N*4];
void up(int u) {
    t[u].mn.fi = a[t[ls].mn.fi] <= a[t[rs].mn.fi] ? t[ls].mn.fi : t[rs].mn.fi;
    t[u].mn.se = a[t[ls].mn.se] < a[t[rs].mn.se] ? t[ls].mn.se : t[rs].mn.se;
    t[u].sum = t[ls].sum + t[rs].sum;
}
void build(int u,int l,int r) {
    if( l == r ) { t[u] = {1,MP(l,l)}; return; }
    build(ls,l,mid), build(rs,mid+1,r);
    up(u);
}
void erase(int u,int l,int r,int p) {
    if( l == r ) { t[u] = {0,MP(0,0)}; return; }
    if( p <= mid ) erase(ls,l,mid,p);
    else erase(rs,mid+1,r,p);
    up(u);
}
int query(int u,int l,int r,int ql,int qr) {
    if( ql > qr ) return 0;
    if( ql <= l && r <= qr ) return t[u].sum;
    int res = 0;
    if( ql <= mid ) res = query(ls,l,mid,ql,qr);
    if( mid < qr ) res += query(rs,mid+1,r,ql,qr);
    return res;
}

signed main() {
    read(n);
    a[0] = 0x3f3f3f3f;
    For(i,1,n) read(a[i]);
    build(1,1,n);
    For(i,1,n) {
        PII u = t[1].mn;
        int sl = query(1,1,n,1,u.fi-1), sr = query(1,1,n,u.se+1,n);
        ans += min(sl,sr);
        erase(1,1,n,sl<sr?u.fi:u.se);
    }
    write(ans);
    return iocl();
} T3

const int N = 6e5+5;
int n,m;
struct Node { int l,r,val; } a[N];
bool operator < (const Node &x,const Node &y)
    { return x.r-x.l!=y.r-y.l ? x.r-x.l>y.r-y.l : mt()&1; }

int fa[N],h[N];
LL ans;
vector<int> to[N];
priority_queue<LL> tmp,pq[N];

#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
namespace seg {
int t[N*4];
void down(int u) { if( ~t[u] ) t[ls] = t[rs] = t[u], t[u] = -1; }
void modify(int u,int l,int r,int ql,int qr,int x) {
    if( ql <= l && r <= qr ) { t[u] = x; return; }
    down(u);
    if( ql <= mid ) modify(ls,l,mid,ql,qr,x);
    if( mid < qr ) modify(rs,mid+1,r,ql,qr,x);
}
int query(int u,int l,int r,int p) {
    if( l == r ) return t[u];
    down(u);
    return p<=mid ? query(ls,l,mid,p) : query(rs,mid+1,r,p);
}
}
#undef ls
#undef rs
#undef mid

void dfs(int u) {
    for(int v : to[u]) dfs(v), ckmax(h[u],h[v]);
    for(int &v : to[u]) if( h[v] == h[u] ) {
        swap(pq[v],pq[u]), v = -1;
        break;
    }
    ++h[u];
    for(int v : to[u]) if( ~v ) {
        while( !pq[v].empty() )
            tmp.push(pq[u].top()+pq[v].top()),
            pq[u].pop(), pq[v].pop();
        swap(pq[u],tmp);
        while( !tmp.empty() ) pq[u].push(tmp.top()), tmp.pop();
    }
    pq[u].push(a[u].val);
}

signed main() {
    read(n,m);
    For(i,1,m) read(a[i].l,a[i].r,a[i].val);
    sort(a+1,a+m+1);
    // For(i,1,m) rFor(j,i-1,1) if( a[j].l <= a[i].l && a[i].r <= a[j].r )
    //  { fa[i] = j; break; }
    // For(i,1,m) to[fa[i]].pb(i);
    For(i,1,m) {
        fa[i] = seg::query(1,1,n,a[i].l), to[fa[i]].pb(i);
        seg::modify(1,1,n,a[i].l,a[i].r,i);
    }
    dfs(0);
    For(i,1,m) {
        pq[0].push(0);
        ans += pq[0].top(), pq[0].pop();
        write(ans,' ');
    }
    return iocl();
}