首页 > 其他分享 >CF1558D

CF1558D

时间:2022-11-03 14:56:31浏览次数:40  
标签:ch int void CF1558D sgt inline mod

这题最终顺序显然无关,只需要考虑顺次加入的每个值的数值即可。
然后如果是操作 \(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

相关文章