差分数组例题：P1083 借教室

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
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[1000000],b[1000000],c[1000000],d[1000000],x[1000000],y[1000000],n,m;
bool check(int k)
{
	memset(b, 0, sizeof(b));
	for (int i = 1; i <= k; i++)
	{
		b[x[i]] += d[i];
		b[y[i]+1] -= d[i];
	}
	for (int i = 1; i <= n; i++)
	{
		c[i] = c[i - 1] + b[i];
		if (c[i] > a[i])return 0;
	}
	return 1;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++)scanf("%d %d %d", &d[i], &x[i], &y[i]);
	int l = 1, r = m;
	while (l < r)
	{
		int mid = (l + r) / 2;
		if (check(mid))l = mid + 1;
		else r = mid;
	}
	if (l == m)cout << "0";
	else cout << -1 << endl << l;
}

单调数组数组例题：P1886 滑动窗口

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
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
deque<int> Max;
deque<int> Min;
int n, k, a[10000000],Maxans[10000000], Minans[10000000];
void MAXmoveR(int x)
{
	if (Max.empty())
	{
		Max.push_back(x);
		return;
	}
	while (!Max.empty() && a[Max.back()] <= a[x])Max.pop_back();
	if(Max.empty() || (!Max.empty() && a[Max.back()] >= a[x]))Max.push_back(x);
}
void MAXmoveL(int x)
{
	if (!Max.empty() && Max.front() < x)Max.pop_front();
}
void MINmoveR(int x)
{
	if (Min.empty())
	{
		Min.push_back(x);
		return;
	}
	while (!Min.empty() && a[Min.back()] >= a[x])Min.pop_back();
	if (Min.empty() || (!Min.empty() && a[Min.back()] <= a[x]))Min.push_back(x);
}
void MINmoveL(int x)
{
	if (!Min.empty() && Min.front() < x)Min.pop_front();
}
int main()
{
	scanf("%d%d", &n ,&k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= k; i++)MAXmoveR(i), MINmoveR(i);
	for (int i = k+1; i <= n; i++)
	{
		Maxans[++Maxans[0]] = a[Max.front()];
		Minans[++Minans[0]] = a[Min.front()];
		MAXmoveL(i - k + 1); MINmoveL(i - k + 1);
		MAXmoveR(i);MINmoveR(i);
		
	}
	Maxans[++Maxans[0]] = a[Max.front()];
	Minans[++Minans[0]] = a[Min.front()];
	for (int i = 1; i <= Minans[0]; i++)printf("%d ", Minans[i]);
	printf("\n");
	for (int i = 1; i <= Maxans[0]; i++)printf("%d ", Maxans[i]);
	//system("pause");
}

ST表:P3865 【模板】ST表

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
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[100001], st[100001][100],n,m;
void prework()
{
	for (int i = 1; i <= n; i++)st[i][0] = a[i];
	for (int j = 1; j <= log2(n); j++)
		for (int i = 1; i <= n - (1 << j) + 1; i++)
			st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int ask(int l, int r)
{
	int k = log2(r - l + 1);
	return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	prework();
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", ask(l, r));
	}
	
}