题解：CF1085G Beautiful Matrix

· · 题解

Solution

这种奶龙题目是怎么被评上黑题的？

考虑你怎么对 \le A 的东西进行计数，其中 \le 表示的是字典序。方法基本上都是，先固定一个前缀和 A 相同，再枚举前缀的下一位使他比 A 小。在本题中，这种方法计算总量为 O(n^3)，显然不能通过。

不过我们假装 n \le 500，看剩下的怎么算。

容易发现，如果我们在 i 行，那么剩下 n-i 行每一行都是一个错排，所以乘上 D(n)^{n-i}，剩下的只需要考虑第 i 行内部的事（D(n) 是错排数。）

假设我们在第 j 列填了 k。

如果 i=1，剩下的 n-j 个数可以随便填，所以方案数是 (n-j)!；否则，剩下的 n-j 个数中，有 t 个不能放在自己对应的位置下面。

设 dp_{i,j} 表示，有 i 个数，其中有 j 个数不能填在特定的位置（这些位置互不相同）的方案数。类似错排，很容易写出递推式：

dp_{i,j} = (j-1) dp_{i-1,j_2} + (i-j) dp_{i-1,j-1}

所以乘上 dp_{n-j,t} 即可。

而 t 是什么呢？容易发现，实际上就是不在集合 \{a_{i-1,1},a_{i,1},\cdots,a_{i-1,j},k\} 中的元素个数。

令 S=\{a_{i-1,1},a_{i,1},\cdots,a_{i-1,j}\}。那么我们需要求出对于所有 < a_{i,j} 且未在 \{a_{i,1},\cdots,a_{i,j-1}\} 中出现的 k，求出 S \cup \{k\} 的集合大小。发现这个只有两种情况，分别是 |S| 和 |S|+1，使用树状数组统计一下即可。

复杂度 O(n^2 \log n)。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e7+10,MAXM=4e5+10;
const double alpha=1.0-sqrt(2.0)/2.0;
struct Node {int lson,rson,sze,sum;bool flp;}t[MAXN];
int rt,n,q,tot,rev[MAXM],ori[MAXM];
int get_node(void) {return ++tot;}
int push_up(int u,int v) {
    int rt=get_node();
    return t[rt]={u,v,t[u].sze+t[v].sze,t[u].sum+t[v].sum,0},rt;
}
int add_tag(int u) {
    if(!u) return 0;
    int rt=get_node();
    return t[rt]=t[u],swap(t[rt].lson,t[rt].rson),t[rt].flp^=1,rt;  
}
void push_down(int u) {
    if(t[u].flp) t[u].flp=0,t[u].lson=add_tag(t[u].lson),t[u].rson=add_tag(t[u].rson);
    return ;
}
int merge(int u,int v) {
    if(!u||!v) return u|v;
    if(t[u].sze>=(t[u].sze+t[v].sze)*alpha&&t[v].sze>=(t[u].sze+t[v].sze)*alpha) return push_up(u,v);
    if(t[u].sze<=t[v].sze) {
        push_down(v);
        int l=t[v].lson,r=t[v].rson;
        if(t[r].sze>=(t[u].sze+t[v].sze)*alpha&&t[l].sze+t[u].sze>=(t[u].sze+t[v].sze)*alpha) return merge(merge(u,l),r);
        push_down(l);
        int ll=t[l].lson,rr=t[l].rson;
        return merge(merge(u,ll),merge(rr,r));
    }
    else {
        push_down(u);
        int l=t[u].lson,r=t[u].rson;
        if(t[l].sze>=(t[u].sze+t[v].sze)*alpha&&t[r].sze+t[v].sze>=(t[u].sze+t[v].sze)*alpha) return merge(l,merge(r,v));
        push_down(r);
        int ll=t[r].lson,rr=t[r].rson;
        return merge(merge(l,ll),merge(rr,v));
    }
}
void split(int u,int v,int &x,int &y) {
    if(!u) return x=y=0,void();
    if(!v) return x=0,y=u,void();
    if(v==t[u].sze) return x=u,y=0,void();
    push_down(u);
    if(v<=t[t[u].lson].sze) return split(t[u].lson,v,x,y),y=merge(y,t[u].rson),void();
    return split(t[u].rson,v-t[t[u].lson].sze,x,y),x=merge(t[u].lson,x),void();
}
int find_pos(int u,int v) {
    push_down(u);
    if(t[u].lson==0) return 1;
    if(t[t[u].lson].sum>=v) return find_pos(t[u].lson,v);
    return find_pos(t[u].rson,v-t[t[u].lson].sum)+t[t[u].lson].sze;
}
void del(int l,int r) {
    int A,B,C;
    split(rt,r,A,C),split(A,l-1,A,B);
    return rt=merge(A,C),void();
}
int nflp[50],flp[50];
void copy(int l,int r,int k,int op) {
    int A,B,C;
    split(rt,r,A,C),split(A,l-1,A,B);
    nflp[0]=B;
    int empt=0;
    int mx=log2(k)+1;
    if(op==0) {
        ffor(i,1,mx) nflp[i]=merge(nflp[i-1],nflp[i-1]);
        ffor(i,0,mx) if(k&(1<<i)) empt=merge(empt,nflp[i]);
        return rt=merge(merge(A,empt),C),void();
    }
    else {
        flp[0]=add_tag(B);
        ffor(i,1,mx) flp[i]=merge(flp[i-1],nflp[i-1]),nflp[i]=merge(nflp[i-1],flp[i-1]);
        int empt=0,cnt=0;
        roff(i,mx,0) if(k&(1<<i)) {
            if(cnt) empt=merge(empt,flp[i]);
            else empt=merge(empt,nflp[i]);
            cnt^=1;
        }
        return rt=merge(merge(A,empt),C),void();
    }
}
void build(int k,int l,int r) {
    tot=max(tot,k);
    int mid=l+r>>1;
    if(l==r) return t[k]={0,0,1,ori[l],0},void();
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);    
    t[k]={k<<1,k<<1|1,t[k<<1].sze+t[k<<1|1].sze,t[k<<1].sum+t[k<<1|1].sum,0};
    return ;
}
string S;
void output(int rt) {
    if(t[rt].lson==0) return cout<<t[rt].sum,void();
    output(t[rt].lson),output(t[rt].rson);
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>S,S="&"+S;
    ffor(i,1,n) ori[i]=S[i]-'0';
    build(1,1,n),rt=1;
    cin>>q;
    ffor(i,1,q) {
        int op; cin>>op;
        if(op==1) {int l,r,k;cin>>l>>r>>k,copy(l,r,k,0);}
        if(op==2) {int l,r,k;cin>>l>>r>>k,copy(l,r,k,1);}
        if(op==3) {int l,r;cin>>l>>r,del(l,r);}
        if(op==4) {
            int pos; cin>>pos;
            if(pos>t[rt].sum) cout<<-1<<'\n'; else cout<<find_pos(rt,pos)<<'\n';    
        }
    }
    return 0;
}