与值域有关的问题（非权值线段树）——运用分块：1004T1

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133560662

  • 区间小于等于某值

  • 区间加

显然同时涉及区间和值域，不能用log级ds来做，常见套路就是上分块

这题是个复合题，后面就是个组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 200010
//#define M
#define mo 998244353
int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		a*=a; b>>=1; 
		ans%=mo; a%=mo; 
	}
	return ans; 
}
int fac[N], inv[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i=fac[0]=1; i<=n; ++i) fac[i]=fac[i-1]*i%mo; 
	ifac[n]=pw(fac[n], mo-2); 
	for(i=n-1; i>=0; --i) ifac[i]=ifac[i+1]*(i+1)%mo; 
    for(i=1; i<=n; ++i) inv[i]=ifac[i]*fac[i-1]%mo; 
}
int C(int n, int m) {
//	if(m>n) return 0;
	return fac[n]*ifac[m]%mo*ifac[n-m]%mo; 
}
const int iv2=pw(2, mo-2); 
struct node { int x, id; } b[N];
struct Node { int k, s, id, ans; } d[N];
int n, m, i, j, k, T;
int l, r, nw, q, op, L, R, pp; 
int tag[N], a[N], x; 

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
		freopen("cook.in", "r", stdin);
	freopen("cook.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); m=sqrt(n); init(2*n); 
//	printf(">> %lld\n", m); 
	
	for(i=1; i<=n; ++i) a[i]=read(); 
	for(l=1; l<=n; l=r+1) {
		r=min(n, (l/m+1)*m); tag[(l-1)/m+1]=0; 
//		printf("[%lld %lld]\n", l, r); 
		for(j=l; j<=r; ++j) b[j].x=a[j], b[j].id=j; 
		sort(b+l, b+r+1, [] (node x, node y) { return x.x<y.x; }); 
	}
//	for(i=1; i<=n; ++i) printf("%lld ", b[i].x); printf("\n"); 
	
	auto work = [&] (int k) -> void {
		int st=(k-1)*m+1, ed=k*m; 
//		printf("# %d [%d %d] %d %d\n", k, st, ed, l, r); 
		for(int j=st; j<=ed; ++j) 
			if(b[j].id>=l && b[j].id<=r) b[j].x+=x; 
		sort(b+st, b+ed+1, [] (node x, node y) { return x.x<y.x; }); 
	}; 
	auto find = [&] (int k, int t) -> int {
		int st=max(l, (k-1)*m+1), ed=min(r, k*m); 
		if(b[st].x>t) return 0; 
		while(st<ed) {
			int mid=(st+ed+1)>>1; 
			if(b[mid].x<=t) st=mid; 
			else ed=mid-1; 
		}
		return st-max(l, (k-1)*m+1)+1; 
	}; 
	auto calc = [&] (int k) -> int {
		int st=(k-1)*m+1, ed=k*m, ans=0; 
		for(int j=st; j<=ed; ++j) 
			if(b[j].id>=l && b[j].id<=r && b[j].x+tag[k]<=x) ++ans; 
		return ans; 
	}; 
	
	for(i=1, j=0; i<=q; ++i) {
		op=read(); l=read(); r=read(); 		
		L=((l-1)/m+1); R=((r-1)/m+1); 
		if(op==1) {	
			x=read(); 
			for(pp=L+1; pp<=R-1; ++pp) tag[pp]+=x; 
			work(L); if(L!=R) work(R); 
//			for(pp=1; pp<=n; ++pp) printf("%d ", b[pp].x+tag[pp/m+1]); printf("\n"); 
		}	
		else {
			x=read(); d[++j].k=read(); d[j].id=i; 
			for(pp=L+1; pp<=R-1; ++pp) d[j].s+=find(pp, x-tag[pp]); 
			d[j].s+=calc(L); if(L!=R) d[j].s+=calc(R); 
			d[j].k=min(d[j].k, d[j].s); 
		}
//		printf("%d [%d %d] %d\n", op, l, r, d[j].s); 

	}
	
//	printf("# %lld\n", j); 

	auto cmp = [&] (Node x, Node y) -> bool {
		if(x.s/m==y.s/m) return x.k<y.k; 
		return x.s/m<y.s/m; 
	}; 
	
	sort(d+1, d+j+1, cmp); 
	for(i=1, l=r=1, nw=2; i<=j; ++i) {
		while(l<d[i].s) nw=(2*nw-C(l, r))%mo, ++l; 
		while(l>d[i].s) --l, nw=(nw+C(l, r))*iv2%mo; 
		while(r<d[i].k) nw=(nw+C(l, r+1))%mo, ++r; 
		while(r>d[i].k) nw=(nw-C(l, r))%mo, --r; 
//		printf("S(%lld %lld)=%lld\n", d[i].s, d[i].k, nw); 
		nw=(nw%mo+mo)%mo; 
		d[i].ans=nw; 
	}
	sort(d+1, d+j+1, [] (Node x, Node y) { return x.id<y.id; }); 
	for(i=1; i<=j; ++i) printf("%lld\n", d[i].ans); 
	return 0;
}