这题最终顺序显然无关,只需要考虑顺次加入的每个值的数值即可。
然后如果是操作 \(1\) 就会产生 \(a_i \leq a_i+1\) 的关系, 如果是操作 \(2\) 就会在插入位置 \(y\) 前增加一个 \(a_y<a_{y+1}\) 最后序列就是 \(a_1<a_2 \leq a_3... \leq a_n\)。
#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x,y,z) for(RG int x=y;x<=z;++x)
#define D(x,y,z) for(RG int x=y;x>=z;--x)
using namespace std;
template <typename T> void read(T &n){ bool f = 1; char ch = getchar(); n = 0; for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 0; for (; isdigit(ch); ch = getchar()) n = (n << 1) + (n << 3) + (ch ^ 48); if (f == 0) n = -n;}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}
const int N = 1e6 + 10, mod = 998244353;
int ans = 0, T, n, m;
LL fac[N], ifac[N];
inline LL Qpow(LL a, int b) {
LL res = 1;
for (; b; b >>= 1) {
if (b & 1) (res *= a) %= mod;
(a *= a) %= mod;
}
return res;
}
inline LL C(int n, int m) {
if (n < m) return 0;
if (n < 0) return 0;
return fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
struct Segment_Tree {
struct info {
int sum, tag, ztag;
}a[N << 3];
#define lson (pos << 1)
#define rson (pos << 1 | 1)
inline void push_up(int pos) {
a[pos].sum = a[lson].sum + a[rson].sum;
a[pos].tag = a[lson].tag + a[rson].tag;
}
inline void push_down(int pos) {
if (!a[pos].ztag) return ;
a[pos].ztag = 0;
a[lson] = a[rson] = (info){0, 0, 1};
}
inline void modify(int pos, int l, int r, int k, int p) {
if (l == r) {
if (p == 0) a[pos].sum = 1;
else if (p == 1) a[pos].tag = 1;
// else
return ;
}
push_down(pos);
int mid = l + r >> 1;
int tmp = (mid - l + 1) - a[lson].sum;
// cout << "chk " << mid - l + 1 << " " << a[lson].sum << " " << tmp << "\n";
if (tmp >= k) modify(lson, l, mid, k, p);
else modify(rson, mid + 1, r, k - tmp, p);
push_up(pos);
}
}sgt;
#define pii pair<int, int>
#define fi first
#define se second
pii q[N];
inline void solve() {
read(n), read(m);
// Segment_Tree sgt;
U(i, 1, m) {
read(q[i].fi), read(q[i].se);
}
D(i, m, 1) {
// pii x
sgt.modify(1, 1, n, q[i].se + 1, 1);
sgt.modify(1, 1, n, q[i].se, 0);
}
writeln(C(n + n - 1 - sgt.a[1].tag, n));
sgt.a[1].sum = sgt.a[1].tag = 0;
sgt.a[1].ztag = 1;
}
int main() {
// FO("");
read(T);
ifac[0] = 1;
fac[0] = 1;
U(i, 1, N - 10) fac[i] = fac[i - 1] * i % mod;
ifac[N - 10] = Qpow(fac[N - 10], mod - 2);
D(i, N - 11, 1) ifac[i] = ifac[i + 1] * (i + 1) % mod;
while (T--) solve();
return 0;
}
标签:ch,int,void,CF1558D,sgt,inline,mod
From: https://www.cnblogs.com/SouthernWay/p/16854430.html