0828考试总结
考崩了，本来以为自己可以考到190或者更高分，实则就拿到了30分。T1统计答案有点问题，最简单的题就拿了30分。T2复杂度没有问题，将点标记上出了问题，爆0了。T3的30分暴力分也没拿到。
T1
是一道枚举+乱搞的题。
先枚举根节点，然后贪心的处理处每个节点的最小深度，暴力统计答案就好。
T2
STL。
用到了(map)，(multiset)，炒鸡香，既简单又便捷。
mp.insert(a)：在mp里插入一个值a；
mp.lower_bound(a)：返回mp种第一个大于等于a的迭代器指针；
mp.upper_bound(a)：返回mp中第一个大于a的迭代器指针；
mp.begin()：头； mp.end()：尾的后一个。
(multiset)插入一个数，删除一个数都是(O(logn))的，它可以保证序列中的数是有序的，序列中可以有重复的数。
mset.insert(a)：插入一个数a；
mset.erase(a)：删除一个数a；
mset.begin()：头； mset.end()：尾的后一个；
mset.size()：返回当前的元素数量；
mset.erase(beg, end)：移除区间[beg,end)中所有的元素。
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e5 + 5;
int n, m;
map <int, multiset<int> > mx, my;
void init() {
n = read(); m = read();
for(int i = 1, x, y;i <= n; i++) {
x = read(); y = read();
mx[x].insert(y);
my[y].insert(x);
}
}
void work() {
for(int i = 1, o, n1, n2;i <= m; i++) {
o = read(); n1 = read(); n2 = read();
int tot = 0;
if(o == 0) {
map <int, multiset<int> > :: iterator it, it1, it2;
it1 = mx.lower_bound(n1);
it2 = mx.upper_bound(n2);
for(it = it1; it != it2; it++) {
multiset<int> &now = (it -> second);
int x = (it -> first);
tot += now.size();
for(multiset <int> :: iterator it = now.begin(); it != now.end(); it++) {
int y = *it;
my[y].erase(x);
}
}
mx.erase(it1, it2);
}
if(o == 1) {
map <int, multiset<int> > :: iterator it, it1, it2;
it1 = my.lower_bound(n1);
it2 = my.upper_bound(n2);
for(it = it1; it != it2; it++) {
multiset<int> &now = (it -> second);
int y = (it -> first);
tot += now.size();
for(multiset <int> :: iterator it = now.begin(); it != now.end(); it++) {
int x = *it;
mx[x].erase(y);
}
}
my.erase(it1, it2);
}
printf("%d
", tot);
}
}
int main() {
freopen("city.in","r",stdin); freopen("city.out","w",stdout);
init();
work();
fclose(stdin); fclose(stdout);
return 0;
}
T3
动态开点线段树+线段树合并。（我吐了）
我太弱了，不咋会。
这道题是在树上找两条最长上升的链，用权值线段树维护一下最长上升的链的长度。
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e5 + 5, inf = 1e9;
int n, cnt, ans, tot;
int root[N][2];
vector<int> e[N];
struct node { int fa, val; } a[N];
struct tree { int ls, rs, sum; } t[N << 2];
void init() {
n = read();
for(int i = 1;i <= n; i++) {
a[i].val = read(); a[i].fa = read();
if(a[i].fa) e[a[i].fa].push_back(i);
}
}
void insert(int &o, int l, int r, int p, int w) {
if(!o) o = ++tot;
t[o].sum = max(t[o].sum, w);
if(l == r) return ;
if(p <= mid) insert(t[o].ls, l, mid, p, w);
if(p > mid) insert(t[o].rs, mid + 1, r, p, w);
}
int query(int o, int l, int r, int x, int y) {
int res = 0;
if(!o) return 0;
if(l >= x && r <= y) return t[o].sum;
if(x <= mid) res = max(res, query(t[o].ls, l, mid, x, y));
if(y > mid) res = max(res, query(t[o].rs, mid + 1, r, x, y));
return res;
}
void merge(int &l, int r) {
if(!l) { l = r; return ; }
if(!r) return ;
t[l].sum = max(t[l].sum, t[r].sum);
merge(t[l].ls, t[r].ls);
merge(t[l].rs, t[r].rs);
}
void dfs(int x) {
insert(root[x][0], 0, inf, a[x].val, 1);
insert(root[x][1], 0, inf, a[x].val, 1); //在权值线段树上插入一个新节点
int tmp1 = 0, tmp2 = 0;
for(int i = 0; i < (int)e[x].size(); i++) {
int y = e[x][i]; dfs(y);
tmp1 = max(tmp1, query(root[y][0], 0, inf, 0, a[x].val - 1)); //询问最大值
tmp2 = max(tmp2, query(root[y][1], 0, inf, a[x].val + 1, inf));
merge(root[x][0], root[y][1]); //合并父亲和儿子的信息
merge(root[x][1], root[y][1]);
}
insert(root[x][0], 0, inf, a[x].val, tmp1 + 1);
insert(root[x][1], 0, inf, a[x].val, tmp2 + 1);
ans = max(ans, tmp1 + tmp2 + 1);
}
void work() {
dfs(1);
printf("%d", ans);
}
int main() {
// freopen("lil.in","r",stdin); freopen("lil.out","w",stdout);
init();
work();
// fclose(stdin); fclose(stdout);
return 0;
}