学习笔记（二） 区间问题

一、ST表（RMQ或RGQ问题等）

ST算法处理静态空间的RMQ问题效率相当高，预处理时间复杂度 O(nlogn) ，查询时间复杂度 O(1)。思路同莫队算法类似，同为分块+处理，但是ST完全不支持修改，如果只有查询，ST查询效率远高于莫队。

思路：DP预处理（倍增法）+贪心查询

首先，ST需要分块，通过倍增思路分块。第一组全分为长度为1的块，第二组全分为长度为2的块，第三组长度为4，倍增地以此类推。注意这里的分块每个块之间不是完全互斥的，和归并排序中的分组完全相反，这里的分块是分别以每个元素为头找到长度为2^(组数-1) 的块，只要块的尾没到数组的结尾，就把每个元素都找到这样的块。如此，总共需要logn个块，用二维数组存储，应该类似于 dp[logn][n] 这样，dp[i][j] 代表第i+1组中以j为首元素的块，而记载的答案自然为要找的最大值或最小值。

然后，分块思路和存储方式找到了，第一组即 dp[0][j] 自然为原数组。通过转移方程:

dp[i][j]=min{dp[i-1][j],dp[i-1][j+2^(i-1)]}

递推得到全部的信息。转移方程代表第i+1组以j为首元素的块的最小值为上一组可以将其平分的两个块最小值的最小值。

因为最值是符合贪心的，所以只要两个小区间能完全覆盖住大区间（两个小区间重叠也可以），那么就可以贪心的递推。

最后便是如何查询了，按照上述所言，对于L到R之间的最值查询，len=R-L+1，只要找到两个小块重叠刚好完全覆盖这个长度就好，小块的长度x满足 x<=len<=2x 就好，即小块在第log(len)+1组。令k=log(lR-L+1)，那么答案就出来了：

ans=min{dp[k][L],dp[k][R-2^k+1]}

eg.洛谷P2880

附链接https://www.luogu.com.cn/problem/P2880

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 5e4 + 5;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;

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 * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

int n, q;
int l, r;
int Log[N];
int dp1[100][N];
int dp2[100][N];

void init() {
	Log[0] = -1;
	rep(i, 1, n) Log[i] = Log[i >> 1] + 1;
	rep(i, 1, Log[n]) {
		rep(j, 1, n) {
			if (j + (1 << i) - 1 <= n)
				dp1[i][j] = min(dp1[i - 1][j], dp1[i - 1][j + (1 << (i - 1))]);
		}
	}
	rep(i, 1, Log[n]) {
		rep(j, 1, n) {
			if (j + (1 << i) - 1 <= n)
				dp2[i][j] = max(dp2[i - 1][j], dp2[i - 1][j + (1 << (i - 1))]);
		}
	}
}

void solve() {
	int mina, maxa;
	int k = Log[r - l + 1];
	mina = min(dp1[k][l], dp1[k][r - (1 << k) + 1]);
	maxa = max(dp2[k][l], dp2[k][r - (1 << k) + 1]);
	cout << maxa - mina << endl;
}

int main() {
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	n=read();
    q=read();
	rep(i, 1, n)  dp1[0][i] = dp2[0][i] = read();
	init();
	while (q--) {
		l = read();
		r = read();
		solve();
	}
	return 0;
}

同理，求取区间最大公约数问题一样解法。对于离线无需维护数组时用ST算法时间复杂度短且非常好写（只需记住两个dp转移方程就好）。

二、线段树

hdu 4027

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;

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 * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

ll n, m;
ll a[N];
ll tree[N << 2];

ll ls(ll x) {
	return x << 1;
}

ll rs(ll x) {
	return x << 1 | 1;
}

void push_up(ll p) {
	tree[p] = tree[ls(p)] + tree[rs(p)];
}

void addtag(ll p, ll pl, ll pr) {
	if (tree[p] > (pr - pl + 1)) {
		if (pl == pr) {
			tree[p] = (ll)sqrt(tree[p]);
			return;
		}
		ll mid = (pl + pr) >> 1;
		addtag(ls(p), pl, mid);
		addtag(rs(p), mid + 1, pr);
		push_up(p);
	}
}

ll build(ll p, ll pl, ll pr) {
	if (pr == pl) {
		tree[p] = a[pl];
		return tree[p];
	}
	ll mid = (pl + pr) >> 1;
	tree[p] = build(ls(p), pl, mid) + build(rs(p), mid + 1, pr);
	return tree[p];
}

void updata(ll l, ll r, ll p, ll pl, ll pr) {
	if (l <= pl && r >= pr) {
		addtag(p, pl, pr);
		return;
	}
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		updata(l, r, ls(p), pl, mid);
	if (r > mid)
		updata(l, r, rs(p), mid + 1, pr);
	push_up(p);
}

ll sum(ll l, ll r, ll p, ll pl, ll pr) {
	if (l <= pl && r >= pr) {
		return tree[p];
	}
	ll res = 0;
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		res += sum(l, r, ls(p), pl, mid);
	if (r > mid)
		res += sum(l, r, rs(p), mid + 1, pr);
	return res;
}

int main() {
	//ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	ll k = 0;
	while (scanf("%lld", &n) != EOF) {
		for (ll i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		build(1, 1, n);
		scanf("%lld", &m);
		++k;
		cout << "Case #" << k << ":" << endl;
		while (m--) {
			ll t, x, y;
			scanf("%lld%lld%lld", &t, &x, &y);
			if (x > y)
				swap(x, y);
			if (t == 0)
				updata(x, y, 1, 1, n);
			else
				cout << sum(x, y, 1, 1, n) << endl;
		}
	}
	return 0;
}

hdu 4578

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef int ll;
const int modp = 10007;

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 * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

ll n, m;
ll tree1[N << 2];
ll tag1[N << 2];
ll tree2[N << 2];
ll tag2[N << 2];
ll tree3[N << 2];
ll tag3[N << 2];

ll ls(ll x) {
	return x << 1;
}

ll rs(ll x) {
	return x << 1 | 1;
}

void push_up(ll p) {
	tree1[p] = (tree1[ls(p)] + tree1[rs(p)]) % modp;
	tree2[p] = (tree2[ls(p)] + tree2[rs(p)]) % modp;
	tree3[p] = (tree3[ls(p)] + tree3[rs(p)]) % modp;
}


void addtag1(ll p, ll d, ll pl, ll pr) { //加法稍麻烦，参考公式
	tree3[p] = ((tree3[p] + (pr - pl + 1) * d % modp * d % modp * d % modp) % modp + 3 * d *
	            (tree2[p] + tree1[p] * d % modp) % modp) % modp;
	tree2[p] = (tree2[p] + (pr - pl + 1) * d % modp * d % modp + 2 * tree1[p] * d % modp) % modp;
	tree1[p] = (tree1[p] + (pr - pl + 1) * d % modp) % modp;
	tag1[p] = (tag1[p] + d) % modp;
}

void addtag2(ll p, ll d, ll pl, ll pr) { //乘法注意，如果有加法标记，将加法标记也乘上乘法标记
	tag1[p] = (tag1[p] * d) % modp;
	tag2[p] = (tag2[p] * d) % modp;
	tree1[p] = tree1[p] * d % modp;
	tree2[p] = tree2[p] * d % modp * d % modp;
	tree3[p] = tree3[p] * d % modp * d % modp * d % modp;
}

void addtag3(ll p, ll d, ll pl, ll pr) { //change时清空加法和乘法标记
	tag1[p] = tag3[p] = 0;
	tag2[p] = 1;
	tag3[p] = d;
	tree1[p] = (pr - pl + 1) * d % modp;
	tree2[p] = (pr - pl + 1) * d % modp * d % modp;
	tree3[p] = (pr - pl + 1) * d % modp * d % modp * d % modp;
}

void pd1(ll p, ll pl, ll pr) { //加
	if (tag1[p]) {
		ll mid = (pl + pr) >> 1;
		addtag1(ls(p), tag1[p], pl, mid);
		addtag1(rs(p), tag1[p], mid + 1, pr);
		tag1[p] = 0;
	}
}

void pd2(ll p, ll pl, ll pr) { //乘
	if (tag2[p] != 1) {
		ll mid = (pl + pr) >> 1;
		addtag2(ls(p), tag2[p], pl, mid);
		addtag2(rs(p), tag2[p], mid + 1, pr);
		tag2[p] = 1;
	}
}

void pd3(ll p, ll pl, ll pr) { //change
	if (tag3[p]) {
		ll mid = (pl + pr) >> 1;
		addtag3(ls(p), tag3[p], pl, mid);
		addtag3(rs(p), tag3[p], mid + 1, pr);
		tag3[p] = 0;
	}
}

void push_down(ll p, ll pl, ll pr) { //先change然后再乘最后加
	pd3(p, pl, pr);
	pd2(p, pl, pr);
	pd1(p, pl, pr);
}

void build(ll p, ll pl, ll pr) {
	tag1[p] = tag3[p] = 0;
	tag2[p] = 1; //注意乘法标记初值为1
	if (pr == pl) {
		tree1[p] = tree2[p] = tree3[p] = 0;
		return;
	}
	ll mid = (pl + pr) >> 1;
	build(ls(p), pl, mid);
	build(rs(p), mid + 1, pr);
	push_up(p);
}

void updata(ll l, ll r, ll d, ll p, ll pl, ll pr, ll k) {
	if (l <= pl && r >= pr) {
		if (k == 1)
			addtag1(p, d, pl, pr);
		else if (k == 2)
			addtag2(p, d, pl, pr);
		else
			addtag3(p, d, pl, pr);
		return;
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		updata(l, r, d, ls(p), pl, mid, k);
	if (r > mid)
		updata(l, r, d, rs(p), mid + 1, pr, k);
	push_up(p);
}

ll sum(ll l, ll r, ll p, ll pl, ll pr, ll k) {
	if (l <= pl && r >= pr) {
		if (k == 1)
			return tree1[p];
		else if (k == 2)
			return tree2[p];
		else
			return tree3[p];
	}
	push_down(p, pl, pr);
	ll res = 0;
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		res = (res + sum(l, r, ls(p), pl, mid, k)) % modp;
	if (r > mid)
		res = (res + sum(l, r, rs(p), mid + 1, pr, k)) % modp;
	return res % modp;
}

int main() {
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0)
			break;
		build(1, 1, n);
		while (m--) {
			ll op, x, y, d;
			cin >> op >> x >> y >> d;
			if (x > y)
				swap(x, y);
			if (op != 4)
				updata(x, y, d, 1, 1, n, op);
			else {
				cout << sum(x, y, 1, 1, n, d) << endl;
			}
		}
	}
	return 0;
}

洛谷P6242

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 5e5 + 5;
const int INF = 1e9 + 5; //0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;

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 * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

ll n, m;
ll a[N];
ll maa[N << 2];
ll numa[N << 2];
ll mab[N << 2];
ll suma[N << 2];
ll sea[N << 2];
ll tagma[N << 2];
ll tagse[N << 2];
ll taghisma[N << 2];
ll taghisse[N << 2];


ll ls(ll x) {
	return x << 1;
}

ll rs(ll x) {
	return x << 1 | 1;
}

void push_up(ll p) {
	suma[p] = suma[ls(p)] + suma[rs(p)];
	maa[p] = max(maa[ls(p)], maa[rs(p)]);
	mab[p] = max(mab[ls(p)], mab[rs(p)]);
	sea[p] = max(sea[ls(p)], sea[rs(p)]);
	if (maa[ls(p)] == maa[rs(p)]) {
		numa[p] = numa[ls(p)] + numa[rs(p)];
	} else {
		sea[p] = max(sea[p], min(maa[ls(p)], maa[rs(p)]));
		numa[p] = maa[ls(p)] > maa[rs(p)] ? numa[ls(p)] : numa[rs(p)];
	}
}

void addtag(ll p, ll pl, ll pr, ll t1, ll t2, ll t3, ll t4) {
	suma[p] += (t1 * numa[p] + (pr - pl + 1 - numa[p]) * t2);
	mab[p] = max(mab[p], t3 + maa[p]);
	maa[p] += t1;
	if (sea[p] != -INF)
		sea[p] += t2;
	taghisma[p] = max(taghisma[p], tagma[p] + t3), tagma[p] += t1;
	taghisse[p] = max(taghisse[p], tagse[p] + t4), tagse[p] += t2;
}

void push_down(ll p, ll pl, ll pr) {
	ll maxn = max(maa[ls(p)], maa[rs(p)]);
	ll mid = (pl + pr) >> 1;
	if (maxn == maa[ls(p)])
		addtag(ls(p), pl, mid, tagma[p], tagse[p], taghisma[p], taghisse[p]);
	else
		addtag(ls(p), pl, mid, tagse[p], tagse[p], taghisse[p], taghisse[p]);
	if (maxn == maa[rs(p)])
		addtag(rs(p), mid + 1, pr, tagma[p], tagse[p], taghisma[p], taghisse[p]);
	else
		addtag(rs(p), mid + 1, pr, tagse[p], tagse[p], taghisse[p], taghisse[p]);
	tagma[p] = tagse[p] = taghisma[p] = taghisse[p] = 0;
}

void build(ll p, ll pl, ll pr) {
	tagma[p] = tagse[p] = taghisma[p] = taghisse[p] = 0;
	if (pr == pl) {
		mab[p] = maa[p] = suma[p] = a[pl];
		sea[p] = -INF;
		numa[p] = 1;
		return;
	}
	ll mid = (pl + pr) >> 1;
	build(ls(p), pl, mid) ;
	build(rs(p), mid + 1, pr);
	push_up(p);
}

void updata1(ll l, ll r, ll d, ll p, ll pl, ll pr) {
	if (l <= pl && r >= pr) {
		addtag(p, pl, pr, d, d, d, d);
		return;
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		updata1(l, r, d, ls(p), pl, mid);
	if (r > mid)
		updata1(l, r, d, rs(p), mid + 1, pr);
	push_up(p);
}

void updata2(ll l, ll r, ll d, ll p, ll pl, ll pr) {
	if (maa[p] <= d)
		return;
	if (l <= pl && r >= pr && sea[p] < d) {
		addtag(p, pl, pr, d - maa[p], 0, d - mab[p], 0);
		return;
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		updata2(l, r, d, ls(p), pl, mid);
	if (r > mid)
		updata2(l, r, d, rs(p), mid + 1, pr);
	push_up(p);
}

ll sum(ll l, ll r, ll p, ll pl, ll pr) {
	if (l <= pl && r >= pr) {
		return suma[p];
	}
	push_down(p, pl, pr);
	ll res = 0;
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		res += sum(l, r, ls(p), pl, mid);
	if (r > mid)
		res += sum(l, r, rs(p), mid + 1, pr);
	return res;
}

ll qmaxa(ll l, ll r, ll p, ll pl, ll pr) {
	if (l <= pl && r >= pr) {
		return maa[p];
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	ll res = -INF;
	if (l <= mid)
		res = max(qmaxa(l, r, ls(p), pl, mid), res);
	if (r > mid)
		res = max(qmaxa(l, r, rs(p), mid + 1, pr), res);
	return res;
}

ll qmaxb(ll l, ll r, ll p, ll pl, ll pr) {
	if (l <= pl && r >= pr) {
		return mab[p];
	}
	push_down(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	ll res = -INF;
	if (l <= mid)
		res = max(qmaxb(l, r, ls(p), pl, mid), res);
	if (r > mid)
		res = max(qmaxb(l, r, rs(p), mid + 1, pr), res);
	return res;
}

int main() {
	n = read();
	m = read();
	for (ll i = 1; i <= n; i++)
		a[i] = read();
	build(1, 1, n);
	while (m--) {
		ll op, x, y;
		op = read();
		x = read();
		y = read();
		if (op == 1) {
			ll d;
			d = read();
			updata1(x, y, d, 1, 1, n);
		} else if (op == 2) {
			ll d;
			d = read();
			updata2(x, y, d, 1, 1, n);
		} else if (op == 3) {
			cout << sum(x, y, 1, 1, n) << endl;
		} else if (op == 4) {
			cout << qmaxa(x, y, 1, 1, n) << endl;
		} else {
			cout << qmaxb(x, y, 1, 1, n) << endl;
		}
	}
	return 0;
}

hdu1540

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 5e4 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef int ll;
const int modp = 1e6 + 37;

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 * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

ll n, m;
ll tree[N];
stack<ll> st;

void init() {
	memset(tree, 0, sizeof(tree));
	rep(i, 1, n) tree[i] = lowbit(i);
	while (!st.empty())
		st.pop();
}

void updata(ll x, ll d) {
	while (x <= n) {
		tree[x] += d;
		x += lowbit(x);
	}
}

ll sum(ll x) {
	ll res = 0;
	while (x > 0) {
		res += tree[x];
		x -= lowbit(x);
	}
	return res;
}

bool check(ll l, ll r) {
	if (sum(r) - sum(l - 1) >= r - l + 1)
		return true;
	return false;
}

ll solve(ll x) {
	ll res = 0;
	ll l = 1, r = x + 1;
	while (l < r) {
		ll mid = (l + r) >> 1;
		if (check(mid, x))
			r = mid;
		else
			l = mid + 1;
	}
	ll pos1 = r;
	l = x;
	r = n;
	while (l < r) {
		ll mid = (l + r + 1) >> 1;
		if (check(x, mid))
			l = mid;
		else
			r = mid - 1;
	}
	ll pos2 = l;
	return pos2 - pos1 + 1;
}

int main() {
	//ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	while (~scanf("%d%d", &n, &m)) {
		init();
		while (m--) {
			char op[10];
			scanf("%s", op);
			if (op[0] == 'D') {
				ll x;
				scanf("%d", &x);
				updata(x, -1);
				st.push(x);
			} else if (op[0] == 'Q') {
				ll x;
				scanf("%d", &x);
				ll ans = solve(x);
				printf("%d\n", ans);
			} else {
				ll x;
				x = st.top();
				st.pop();
				updata(x, 1);
			}
		}
	}
	return 0;
}

hdu 1542

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 5e3 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;

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 * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

ll n;
double tree[N << 2];
int tag[N << 2];
double xx[N];

typedef struct scanl {
	double x1, x2, y;
	int io;
	bool operator <(const scanl &a) {
		return y < a.y;
	}
	scanl() {
	}
	scanl(double xx1, double xx2, double yy, int iio) {
		x1 = xx1, x2 = xx2, y = yy, io = iio;
	}
} Line;

Line line[N];

ll ls(ll p) {
	return p << 1;
}

ll rs(ll p) {
	return p << 1 | 1;
}

void push_up(ll p, ll pl, ll pr) {
	if (tag[p] > 0)
		tree[p] = xx[pr] - xx[pl];
	else if (pl + 1 == pr)
		tree[p] = 0;
	else
		tree[p] = tree[ls(p)] + tree[rs(p)];
}

void addtag(ll p, ll d, ll pl, ll pr) {
	tag[p] += d;
	if (tag[p] > 0)
		tree[p] = xx[pr] - xx[pl];
	else if (pl + 1 == pr)
		tree[p] = 0;
	else
		tree[p] = tree[ls(p)] + tree[rs(p)];
}

void updata(ll l, ll r, ll d, ll p, ll pl, ll pr) {
	if (l <= pl && r >= pr) {
		addtag(p, d, pl, pr);
		return;
	}
	if (pl + 1 == pr)
		return;
	ll mid = (pl + pr) >> 1;
	if (l <= mid)
		updata(l, r, d, ls(p), pl, mid);
	if (r > mid)
		updata(l, r, d, rs(p), mid, pr);
	push_up(p, pl, pr);
}


int main() {
	//ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	int k = 0;
	while (~scanf("%d", &n)) {
		if (n == 0)
			break;
		int cnt = 0;
		rep(i, 1, n) {
			double x1, x2, y1, y2;
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			line[++cnt] = Line(x1, x2, y1, 1);
			xx[cnt] = x1;
			line[++cnt] = Line(x1, x2, y2, -1);
			xx[cnt] = x2;
		}
		sort(line + 1, line + cnt + 1);
		sort(xx + 1, xx + cnt + 1);
		int num = unique(xx + 1, xx + cnt + 1) - (xx + 1);
		memset(tree, 0, sizeof(tree));
		memset(tag, 0, sizeof(tag));
		double ans = 0;
		rep(i, 1, cnt) {
			ans += tree[1] * (line[i].y - line[i - 1].y);
			int l = lower_bound(xx + 1, xx + num + 1, line[i].x1) - xx;
			int r = lower_bound(xx + 1, xx + num + 1, line[i].x2) - xx;
			updata(l, r, line[i].io, 1, 1, num);
		}
		cout << "Test case #" << ++k << endl;
		printf("Total explored area: %.2lf\n", ans);
	}
	return 0;
}

全部评论

相关推荐

11-21 11:33
安克创新 Anker_嵌入式软件工程师(准入职员工)
点赞 评论 收藏
分享
10-14 21:06
西北农林科技大学 数据分析师
不是哥们
有点夸张了，50K😥
爱吃烤肠的牛油最喜欢...：50K是ssp了估计，ssp的人家多厉害都不用说，每年比例大概在百分之5左右
点赞 评论 收藏
分享
10-21 09:12
上海第二工业大学 嵌入式软件开发
双非秋招闹麻了
未知的命运：大佬这都找不到我还找啥啊
点赞 评论 收藏
分享
11-21 15:55
已编辑
途虎_招聘专员
点赞 评论 收藏
分享
评论
点赞
2
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 你想跟着什么样领导？ #
5732次浏览 82人参与
# 什么样的背景能拿SSP? #
117422次浏览 410人参与
# 百度秋招 #
56094次浏览 394人参与
# 你的秋招白月光和意难平公司 #
7383次浏览 82人参与
# 分享一个让你热爱工作的瞬间 #
47572次浏览 412人参与
# 找实习是选平台还是选业务？ #
10445次浏览 149人参与
# 从夯到拉，评价编程语言 #
5163次浏览 48人参与
# 秋招签约后的心态变化 #
106197次浏览 923人参与
# 职场吐槽大会 #
289900次浏览 2111人参与
# 每个月花钱最多的地方是？ #
5476次浏览 76人参与
# xxx岗位的一天 #
10241次浏览 92人参与
# 作业帮求职进展汇总 #
77790次浏览 520人参与
# 十一月总结 #
13583次浏览 146人参与
# 你面试时吹过最大的牛 #
20464次浏览 116人参与
# 为什么国企只招应届生 #
218591次浏览 1262人参与
# 饿了么求职进展汇总 #
80394次浏览 684人参与
# 非技术求职现状 #
549665次浏览 3509人参与
# 实习学到最有价值的工作习惯 #
43730次浏览 378人参与
# 韶音科技求职进展汇总 #
65115次浏览 510人参与
# AI“智障”时刻 #
6179次浏览 54人参与
# 实习生如何通过转正 #
111890次浏览 1421人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务