题目连接 题意: 给你一个长为n,宽为1,高为无穷的水缸。里面有n-1个高度不一的隔板隔开为1x1大小的区域。里面的水遵循物理定理。给你m次查询和回应，每个查询<x,y,z>。代表查询第x个区域高度为y+0.5的地方，如果z为0，回应为这个位置没有水，如果为z为1，则回应是有水。问：这些回应最多有多少个正确的。 题解： 从这个题就能清楚的看到人与人之间的差距。有的大佬用prioriaty_queue，50line直接通过。有的人用可并堆80line直接通过。有的人用线段树合并，接近200line，wa了10+发后贴着时限通过。
理论上线段树合并应该比prioriaty_queue快才对。一个 O ( n l o g n ) O(nlogn) O(nlogn)，一个 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。实则不是这样。因为我是个憨憨。一个线段树合并都能写出n^2的常数。
首先考虑没有水，那么符合要求的数量即为z=0的数量。对于一次查询。从这个查询区间开始，向右和向左找到第一个大于这次查询高度的隔板。那个这个区间段，就是水位正好处在该次查询是的占有区间段。我们发现一个事实。如果我们把水位从低到高枚举，每个出现过区间段，只会被合并到一个更大的区间段里，不会被再次拆分了。 所以憨憨的我开始了线段树合并。。。首先我们从低到高枚举水位，然后考虑这个合并区间段，然后看一看该区间原先的最好情况，和现在的最好情况的大小。现在的最好情况就是该区间段的所有比这次查询低或相等的1的数量，以及比这次查询高的0的数量之和。如果比原来的情况大。我们的答案就+=现在的情况-原来的情况。因为我们将原来的情况替换为现在的情况。最后就得出答案了。这里使用并查集维护每个区间段的l， r节点以及该区间段的最好情况。用线段树合并维护该区间段的每个高度的1，0数量。
下面是ac代码：
#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); using namespace std; const int N = 2e5 + 5; const int Z = 3e5 + 5; int tot; struct Node { int l, r; int val1, val0; }tr[N * 40]; int cnt, top; int rt[N], bac[N*40]; // rt数组记录每个线段树的根节点 inline int newnod() { return cnt ? bac[cnt--] : ++tot; } // 开点操作 inline void del(int p) { bac[++cnt] = p; tr[p].l = tr[p].r = tr[p].val0 = tr[p].val1 = 0; } // 垃圾回收 inline void pushup(int p) { tr[p].val0 = tr[tr[p].l].val0 + tr[tr[p].r].val0; tr[p].val1 = tr[tr[p].l].val1 + tr[tr[p].r].val1; } void insert(int &p, int pos, int v, int flag, int l = 1, int r = Z) { //cout << pos <<endl; //cout << l << " " << r << endl; if (!p) p = newnod(); if (l == r) { if (flag == 1) tr[p].val1 += v; else tr[p].val0 += v; return; } int mid = (l + r) >> 1; //cout << pos << " " << mid << endl; if (pos <= mid) insert(tr[p].l, pos, v, flag, l, mid); else insert(tr[p].r, pos, v, flag, mid + 1, r); pushup(p); } int merge(int x, int y, int l = 1, int r = Z) { if (!x || !y) return x + y; int mid = (l + r) >> 1; if (l == r) { tr[x].val0 += tr[y].val0; tr[x].val1 += tr[y].val1; } else { tr[x].l = merge(tr[x].l, tr[y].l, l, mid); tr[x].r = merge(tr[x].r, tr[y].r, mid + 1, r); pushup(x); } del(y); return x; } int ask(int p, int l, int r, int cl, int cr, int flag) { if (p == 0) return 0; if(cl <= l && r <= cr) { if (flag == 0) return tr[p].val0; return tr[p].val1; } int mid = (l + r) >> 1; int val = 0; if (cl <= mid) val += ask(tr[p].l, l, mid, cl, cr, flag); if (cr > mid) val += ask(tr[p].r, mid+1, r, cl, cr, flag); return val; } int fa[N]; int fi(int x) { if (fa[x] == x) return x; return fa[x] = fi(fa[x]); } pair<int, int> sg[N]; int good[N]; int su[N]; struct Q { int x, y, z; } q[N]; bool cmp(const Q &a, const Q &b) { return a.y < b.y; } int lisan[N * 3], lcnt; int getn(int x) { return lower_bound(lisan+1, lisan+lcnt, x) - lisan; } int main() { int t; cin >> t; int t0 = 1; while(t--) { tot = cnt = 0; lcnt = 0; int n, m; scanf("%d%d", &n, &m); for (int i = 0; i <= n * 40; i++) tr[i].l = tr[i].r = tr[i].val0 = tr[i].val1 = 0; for (int i = 0; i <= n; i++) fa[i] = i, sg[i].first = sg[i].second = i, rt[i] = 0, good[i] =0; for (int i = 1; i< n; i++) scanf("%d", &su[i]), lisan[++lcnt] = su[i]; int ans = 0; for (int i = 1; i <= m; i++) { scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z); lisan[++lcnt] = q[i].y; if (q[i].z == 0) good[q[i].x]++, ans++; } sort(lisan+1, lisan+lcnt+1); lcnt = unique(lisan+1, lisan+lcnt+1) - lisan; for (int i = 1; i <= m; i++) insert(rt[q[i].x], getn(q[i].y), 1, q[i].z); sort(q+1,q+m+1, cmp); for (int i = 1; i <= m; i++) { if (q[i].z == 0) continue; int _rt = fi(q[i].x); int _l = sg[_rt].first, _r = sg[_rt].second; int res = good[_rt]; while(sg[_rt].first - 1 >= 1 && su[sg[_rt].first - 1] <= q[i].y) { int _x = fi(sg[_rt].first-1); rt[_rt] = merge(rt[_rt], rt[_x]); fa[_x] = _rt; sg[_rt].first = sg[_x].first; res += good[_x]; good[_rt] += good[_x]; } while(sg[_rt].second < n && su[sg[_rt].second] <= q[i].y) { int _x = fi(sg[_rt].second+1); rt[_rt] = merge(rt[_rt], rt[_x]); fa[_x] = _rt; sg[_rt].second = sg[_x].second; res += good[_x]; good[_rt] += good[_x]; } int nres = ask(rt[_rt], 1, Z, getn(q[i].y)+1, Z, 0) + ask(rt[_rt], 1, Z, 1, getn(q[i].y), 1); ask(rt[_rt], 1, Z, 1, getn(q[i].y), 1); if (nres > good[_rt]) { ans += nres - good[_rt]; good[_rt] = nres; } // cout << ans <<endl; } printf("Case #%d: %d\n",t0++, ans); } return 0; }