傳送門

文章目錄

• 題意：
• 思路：

題意：

思路：

考慮最終的序列是什么鴨子的，首先序列肯定單調不降，也就是$a_1\le a_2\le a_3\le ...\le a_n$，顯然不可能都是$\le$號，因為如果插入的話是有可能產生$<$號的。假設我們現在有$x$個$<$ 號，那么應該有$\left(\genfrac{}{}{0ex}{}{n+n?1?x}{n}\right)$個序列，因為我們將$a_i\le a_{i+1}$轉換成$a_i<a_i+1+1$，也就是擴展了一下值域，最多擴展了$n?1?x$個值域，也就是目前值域是$[1,n?2?1?x]$，從中選$n$個數構成一個嚴格遞增的序列方案就是$\left(\genfrac{}{}{0ex}{}{n?2?1?x}{n}\right)$，那么現在問題就是如何知道$x$。

首先插入一組最多能產生一個$<$號，因為有可能若干數插到了同一個數后面，比如這個例子$n=3,m=2,(2,1),(3,2)$，這樣在$a_1$前面插入了兩個數$a_2,a_3$，能確定$a_1>a_2,a_1>a_3$，但是不能確定$a_2$和$a_3$的關系，所以這樣的話我們就認為$a_2,a_3$之間是一個$\le$ 號。我們考慮倒著來處理這$m$組，首先最終序列長度是$n$，假設現在有$(x_i,y_i)$，那么先找到第$y_i$個位置$p$和第$y_i+1$的位置$q$，此時將$p$刪除，將$q$標記一下代表有個數在他前面有$<$即可。至于為什么是$y_i,y_{i+1}$而不是$y_{i?1},y_i$，是因為如果$y_i=1$的時候，$y_i?1=0$，這個時候在線段樹上二分就會出錯。

在線段樹上二分即可。

如果正著來，可以建一個基于權值的平衡樹，讓后模擬插入即可。

由于題目的問題，線段樹不能每次建樹。。。

// Problem: F. Top-Notch Insertions // Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine)) // URL: https://codeforces.com/contest/1561/problem/F // Memory Limit: 512 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=998244353,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; PII p[N]; struct Node {int l,r;int cnt; }tr[N<<2];void pushup(int u) {tr[u].cnt=tr[L].cnt+tr[R].cnt; }void build(int u,int l,int r) {tr[u]={l,r};if(l==r) {tr[u].cnt=1;return;}build(L,l,Mid); build(R,Mid+1,r);pushup(u); }void change(int u,int pos,int x) {if(tr[u].l==tr[u].r) {tr[u].cnt=x;return;}if(pos<=Mid) change(L,pos,x);else change(R,pos,x);pushup(u); }int query(int u,int cnt) {if(tr[u].l==tr[u].r) return tr[u].l;if(cnt<=tr[L].cnt) return query(L,cnt);else return query(R,cnt-tr[L].cnt); }LL fun[N],inv[N];LL qmi(LL a,LL b) {LL ans=1;while(b) {if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }LL C(int a,int b) {if(a<0||b<0||a<b) return 0;return fun[a]*inv[b]%mod*inv[a-b]%mod; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);fun[0]=1;for(int i=1;i<N;i++) fun[i]=fun[i-1]*i%mod;inv[N-1]=qmi(fun[N-1],mod-2);for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;build(1,1,N-1);int _; scanf("%d",&_);while(_--) {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d%d",&p[i].X,&p[i].Y);set<int>s; vector<int>v;for(int i=m;i>=1;i--) {int a=query(1,p[i].Y),b=query(1,p[i].Y+1);change(1,a,0); s.insert(b); v.pb(a);}for(auto x:v) change(1,x,1);int cnt=s.size();printf("%lld\n",C(n*2-1-cnt,n));}return 0; } /**/ // Problem: F. Top-Notch Insertions // Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine)) // URL: https://codeforces.com/contest/1561/problem/F // Memory Limit: 512 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=998244353,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; int root,tot; int x,y; struct Node {int l,r;int size,fa,val,rank,tag; }tr[N];int newnode(int v) {tr[++tot].val=v,tr[tot].size=1,tr[tot].rank=rand();tr[tot].l=tr[tot].r=tr[tot].tag=0;return tot; }void pushup(int u) {if(!u) return;tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+1;// tr[u].val=max(tr[tr[u].l].val,tr[tr[u].r].val); }void pushdown(int u) {if(!u) return;int tag=tr[u].tag; tr[u].tag=0;if(tr[u].l) tr[tr[u].l].tag+=tag,tr[tr[u].l].val+=tag;if(tr[u].r) tr[tr[u].r].tag+=tag,tr[tr[u].r].val+=tag; }void split(int u,int k,int &x,int &y) {if(!u) { x=y=0; return; }pushdown(u);if(tr[u].val<=k) x=u,split(tr[u].r,k,tr[u].r,y);else y=u,split(tr[u].l,k,x,tr[u].l);pushup(u); }int merge(int u,int v) {if(!u||!v) return u+v;if(tr[u].rank<tr[v].rank) {pushdown(u);tr[u].r=merge(tr[u].r,v);pushup(u);return u;}else {pushdown(v);tr[v].l=merge(u,tr[v].l);pushup(v);return v;} }int find(int u,int x) {if(!u) return 0;if(tr[u].val==x) return 1;pushdown(u);if(x<tr[u].val) return find(tr[u].l,x);else return find(tr[u].r,x); }LL fun[N],inv[N];LL qmi(LL a,LL b) {LL ans=1;while(b) {if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }LL C(int a,int b) {if(a<0||b<0||a<b) return 0;return fun[a]*inv[b]%mod*inv[a-b]%mod; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);fun[0]=1;for(int i=1;i<N;i++) fun[i]=fun[i-1]*i%mod;inv[N-1]=qmi(fun[N-1],mod-2);for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;int _; scanf("%d",&_);while(_--) {root=tot=0;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {int a,b; scanf("%d%d",&a,&b);int flag=find(root,b);split(root,b-1,x,y);if(y) tr[y].val++,tr[y].tag++;root=merge(x,flag? y:merge(newnode(b+1),y));}printf("%lld\n",C(n*2-1-tot,n));}return 0; } /**/

總結

以上是生活随笔為你收集整理的Codeforces Round #740 (Div. 2) F. Top-Notch Insertions 线段树 / 平衡树 + 组合数学的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。