關于其實根本不是水題: 我都快改吐了
BZOJ4756 Promotion Counting
裸的線段樹板子，一邊dfs一邊合并，然后找第比自己小的即可
BZOJ4399: 魔法少女LJJ
首先這題可坑了，資料范圍\(c\)<=7
若\(c=1\)，之后一個正整數\(x\)，表示新建一個權值為\(x\)的節點，并且節點編號為\(n+1\)（當前有\(n\)個節點），
若\(c=2\)，之后兩個正整數\(a\)，\(b\)，表示在\(a\)，\(b\)之間連接一條邊，
若\(c=3\)，之后兩個正整數\(a\)，\(x\)，表示\(a\)聯通快內原本權值小于\(x\)的節點全部變成\(x\)，
若\(c=4\)，之后兩個正整數\(a\)，\(x\)，表示\(a\)聯通快內原本權值大于\(x\)的節點全部變成\(x\)，
若\(c=5\)，之后兩個正整數\(a\)，\(k\)，表示詢問\(a\)所屬于的聯通塊內的第\(k\)小的權值是多少，
若\(c=6\)，之后兩個正整數\(a\)，\(b\)，表示詢問\(a\)所屬聯通快內所有節點權值之積與\(b\)所屬聯通快內所有節點權值之積的大小， 若\(a\)所屬聯通快內所有節點權值之積大于b所屬聯通快內所有節點權值之積，輸出\(1\)，否則為\(0\)，
若\(c=7\)，之后一個正整數a，表示詢問a所在聯通塊大小
并查集套線段樹裸題
1:直接新建一顆線段樹即可
2:線段樹合并，因為只考慮聯通塊，所以順序無關
3,4:等價于刪掉指定區間的點，推薦打 lazytag ,或者\(O(1)\)記憶體泄漏\(tree[fa].ch=0\)也行
5:權值線段樹板子
6:小技巧：乘積顯然會爆\(long long\)，因為只需要比較，所以取\(log\)即可
7:并查集直接維護
關于調了一下午:
一些ZZ錯誤
1.忘記\(pushdown\)
2.并查集\(fx = fy\)，聯通塊的點的根一定要用并查集的根!!!!!!!!!!!!!
3.\(pushdown\)沒有清除\(lazy\)
4.\(erase\)沒有判斷是否節點為空,導致復雜度假掉，或者直接RE
1.學到的：洗掉操作可以打\(lazy\)
2.\(kth\)函式可以用回圈
3.可以利用lazy和結束條件大力剪枝
4.其實沒必要抄題解，可能就差一點點
5.erase函式可以記錄一個刪去了幾個點, 省去query
6.想到高精度，可以想想能不能對數
9.其實沒必要離散化，但是可以縮小常數，能離散化還是離散化了好
BZOJ4919 大根堆
這個題其實就是樹上LIS
它的性質是多條鏈狀的LIS，最后合并到一起
方法1：set平衡樹維護Lis陣列，網上題解好多都是這個，平衡樹啟發式合并，不細說
方法2：線段樹合并模擬平衡樹啟發式合并，就是把 lower_bound(a.begin(), a.end(), key) 改成查找小于等于 \(key\) 的數字，然后直接插入即可
方法3：線段樹優化dp
考慮\(O(n^2)\)的暴力dp
首先樹形dp顯然第一維要是點數，考慮第二維，因為對于一個點\(u\)我們要保證它的子結點都比\(u\)小,那么第二維就要考慮子樹內最大值，dp實際含義就是點數
設\(f[i][j]\)為以\(i\)為子樹，子樹內最大值小于等于j時滿足的點數
對于一個根，只有選或者不選兩種情況，如果是選，就要滿足\(j <= val[u]\), 如果不選
不難發現
先考慮不選擇u的情況轉移
\(f(i,j) = \sum_{v \in uson}f(v, j)\)
再轉移選則u的情況
\(f(i,j) = max(f(i, j), f(i,val[u])+1)\)
暴力dp很容易寫出來代碼
$O(n^2)$
void dfs(int u, int fa){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
dfs(v, u);
for(int j = 1; j <= n; ++j){
f[u][j] += f[v][j];
}
}
for(int i = n;i >= v[u]; --i){
f[u][i] = std::max(f[u][i], f[u][v[u]]+1);
}
}
然后我們考慮如何優化它,這個dp只有區間對一個值求max還有區間和相加操作
對于區間和相加，我們可以用線段樹合并維護
對于求max，
由于線段樹動態開點，所以lazytag很難維護，考慮懶惰標記永久化
還有一種方式，我們注意到\(f[i]\)陣列是單調的，我們可以二分，尋找小于\(key\)的區間，將其統一修改成\(key\)，(像極了上面那道題)， 但復雜度是\(O(log^2)\)的
也可以線段樹差分（不過我不會,以后更新）
PS：雖然后兩種方法復雜度更優秀，但是第一種方法常數小，時間更優
LUOGU P4577 領導集團問題
這個題和上面基本一樣，只不過嚴格大于子結點改成了不嚴格小于子結點
LUOGU P4556 雨天的尾巴
luogu 板子題
網上題解很詳細了，直接線段樹差分即可
LUOGU P4219 大融合
不難看出一條邊經過簡單路徑的數量就是它他連接的兩個聯通塊的點數乘積
用并查集維護聯通塊總點數和聯通塊根結點（一定要注意！！！一個聯通塊的合并順序要一定！！！！并查集的根結點和線段樹根結點要對應！！調了好久）
為了方便答案 = （總大小-一部分大小）×這一部分大小
其實就是子樹大小
怎么方便的用線段樹維護子樹大小？
離線，dfs一遍，用dfs序建立線段樹
加邊操作合并線段樹和并查集即可
LUOGU P2605 base 基站選址
大力dp+優化
這題重點在dp, 不在我們討論范圍內
不用線段樹合并即可
LUOGU P5298 minimax
這題很妙，題解很多這里不細說
本題最有意思的技巧是在merge了兩個子樹，并且在merge時候update，而且打了區間lazytag
可以區間操作的原因是因為概率的線性性，區間的概率是單點的概率和
可以在merge時候區間操作也是很妙的，很難想到，由于題目中說任意兩個點權值不同，不可能出現兩個葉子重疊
大力分類：
1.兩邊結點都有值：大力遞回push_up求概率
2.只有一邊有值：通過公式區間更新
3.兩邊都沒值:概率一定是0,因為已經push_down,return
而且:動態開點線段樹區間操作時不能隨便push_down, 否則會導致兒子過多，但是又不能直接忽略lazytag, 線段樹沒有兒子是說兒子和父親的性質一樣，不是說兒子節點為0
一邊Merge一邊維護前綴后綴和也是非常妙的
附錄：AC CODES
T1
#include<cstdio>
#include<algorithm>
#include<cassert>
using std::sort;
const int maxn = 1e6+10, maxtr = 32*maxn;
int ans[maxn];
int roots[maxn];
int a[maxn], b[maxn];
int n;
struct segment_tree{
int tot;
struct node{
int ls, rs, val;
node(){}
node(int a, int b, int c):ls(a), rs(b), val(c){}
}tree[maxtr];
segment_tree(){
tot = 0;
}
int newnode(){
return ++tot;
}
void push_up(int p){
tree[p].val = tree[tree[p].ls].val+tree[tree[p].rs].val;
}
void Modify(int& p, int l, int r, int s){
p = newnode();
// printf("M%d %d %d %d\n", p, l, r, s);
if(l == r && l == s)
return ++tree[p].val, void();
int mid = (l+r)>>1;
if(s <= mid)
Modify(tree[p].ls, l, mid, s);
if(s > mid)
Modify(tree[p].rs, mid+1, r, s);
push_up(p);
}
int Query(int p, int l, int r, int s, int t){
//s結點右邊有多少
if(!p) {
return 0;
}
if(s <= l && r <= t){
return tree[p].val;
}
int mid = (l+r)>>1;
int ans = 0;
if(s <= mid)
ans = Query(tree[p].ls, l, mid, s, t);
if(t > mid)
ans += Query(tree[p].rs, mid+1, r, s, t);
return ans;
}
void merge(int &rt, int p, int l, int r){
if(!p) return;
if(!rt) return rt = p, void();
if(l == r){
return tree[rt].val += tree[p].val, void();
}
int mid = (l+r)>>1;
merge(tree[rt].ls, tree[p].ls, l, mid);
merge(tree[rt].rs, tree[p].rs, mid+1, r);
push_up(rt);
}
}segt;
struct Graph{
struct edge{
int to,nxt;
edge(){}
edge(int a, int b):to(a), nxt(b){}
}e[2*maxn];
int head[maxn];
void ins(int frm, int to){
static int i = 0;
++i;
e[i] = edge(to, head[frm]);
head[frm] = i;
}
void dfs(int u, int fa){
// printf("%d %d", u, fa);
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
dfs(v,u);
segt.merge(roots[u], roots[v], 1, n+1);
}
ans[u] = segt.Query(roots[u], 1, n+1, b[u]+1, n+1);
// printf("ans[%d] = %d\n",u,ans[u]);
}
}G;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d", a+i);
}
for(int i = 2; i <= n; ++i){
int u;
scanf("%d", &u);
G.ins(i, u);
G.ins(u, i);
}
for(int i = 1; i <= n; ++i){
b[i] = a[i];
}
std::sort(a+1, a+1+n);
int len = std::unique(a+1, a+1+n)-a-1;
for(int i = 1; i <= n; ++i){
b[i] = std::lower_bound(a+1, a+1+len, b[i])-a;
}
for(int i = 1; i <= n; ++i){
segt.Modify(roots[i], 1, n+1, b[i]);
}
G.dfs(1, 1);
for(int i = 1; i <= n; ++i){
printf("%d\n", ans[i]);
}
return 0;
}
T2
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cassert>
#include<cmath>
typedef long long ll;
const int maxn = 4e5+10, maxtr = 80*maxn, maxr = 1e9+10;
int tmp[maxn];
int roots[maxn];
int m, n;
int ranger;
struct input{
int opt,x,y;
input(){}
input(int a, int b, int c):opt(a), x(b), y(c){}
}inputs[maxn];
int Query(int x){
return std::lower_bound(tmp+1, tmp+1+tmp[0], x)-tmp;
}
int DeQuery(int x){
return tmp[x];
}
struct ret_t{
int cnt;
double lg;
ret_t():cnt(0),lg(0.0){}
ret_t(double a, int b):cnt(b),lg(a){}
friend ret_t operator +(const ret_t a, const ret_t b){
return ret_t(a.lg+b.lg, a.cnt+b.cnt);
}
};
struct segment_tree{
struct node{
int cnt;
double lg;
bool is_clear;
int ls, rs;
}tree[maxtr];
int tot;
segment_tree(){
tot = 0;
}
int newnode(){
return ++tot;
}
void update(int p, double lg, ll cnt){
tree[p].lg += lg;
tree[p].cnt += cnt;
}
void clear(int p){
tree[p].is_clear = true;
tree[p].lg = 0;
tree[p].cnt = 0;
}
void push_down(int rt){
if(tree[rt].is_clear){
clear(tree[rt].ls);
clear(tree[rt].rs);
tree[rt].is_clear = false;
}
}
void push_up(int rt){
int ls = tree[rt].ls, rs = tree[rt].rs;
tree[rt].lg = tree[ls].lg+tree[rs].lg;
tree[rt].cnt = tree[ls].cnt+tree[rs].cnt;
}
void modify(int &p, int l, int r, int s, double lg, ll cnt){
if(!p) p = newnode();
if(l == r){
return update(p, lg*cnt, cnt);
}
int mid = (l+r)>>1;
push_down(p);
if(s <= mid)
modify(tree[p].ls, l, mid, s, lg, cnt);
if(s > mid)
modify(tree[p].rs, mid+1, r ,s ,lg, cnt);
push_up(p);
}
void merge(int &rt, int p, int l, int r){
if(!p || tree[p].is_clear) return;
if(!rt || tree[p].is_clear) return rt = p, void();
if(l == r)
return update(rt, tree[p].lg, tree[p].cnt);
push_down(rt);
push_down(p);
int mid = (l+r)>>1;
merge(tree[rt].ls, tree[p].ls, l, mid);
merge(tree[rt].rs, tree[p].rs, mid+1, r);
push_up(rt);
}
ret_t query(int &rt, int l, int r, int s, int t){
if(s > t || !rt)
return ret_t();
if(s <= l && r <= t){
return ret_t(tree[rt].lg, tree[rt].cnt);
}
push_down(rt);
int mid = (l+r)>>1;
ret_t ret;
if(s <= mid)
ret = ret+query(tree[rt].ls, l, mid, s, t);
if(t > mid)
ret = ret+query(tree[rt].rs, mid+1, r, s, t);
return ret;
}
int erase(int &p, int l, int r, int s, int t){
int ret = 0;
if(s > t) return 0;
if(!p || tree[p].is_clear) return 0;
//洗掉[s, t]區間
if(s <= l && r <= t)
return ret = tree[p].cnt, clear(p), ret;
int mid = (l+r)>>1;
push_down(p);
if(s <= mid)
ret = erase(tree[p].ls, l, mid, s, t);
if(t > mid)
ret += erase(tree[p].rs, mid+1, r ,s ,t);
push_up(p);
return ret;
}
int kth(int p, int l, int r, int k){
int lsiz = tree[tree[p].ls].cnt;
if(l == r)
return l;
push_down(p);
int mid = (l+r)>>1;
if(k <= lsiz)
return kth(tree[p].ls, l, mid, k);
else
return kth(tree[p].rs, mid+1, r, k-lsiz);
}
}segt;
struct DFU{
int fa[maxn];
int siz[maxn];
void init(int len){
for(int i = 1; i <= len; ++i){
fa[i] = i;
siz[i] = 1;
}
}
int Find(int u){
return u == fa[u]? u : (fa[u] = Find(fa[u]));
}
void merge_s(int fu, int fv){//把fv掛在fu上(已經Find)
segt.merge(roots[fu], roots[fv], 1, ranger);
siz[fu] += siz[fv];
fa[fv] = fa[fu];
}
void merge(int u, int v){
int fu = Find(u), fv = Find(v);
if(fu == fv) return;
int su = siz[fu], sv = siz[fv];
if(su >= sv){
merge_s(fu, fv);
}else{
merge_s(fv, fu);
}
}
int getsiz(int u){
return siz[Find(u)];
}
}un;
void operation_3(int x, int val){
int fx = un.Find(x), p = Query(val);
int mycnt = segt.erase(roots[fx], 1, ranger, 1, p-1);
segt.modify(roots[fx], 1, ranger, p, log(val), mycnt);
}
void operation_4(int x, int val){
int fx = un.Find(x), p = Query(val);
int mycnt = segt.erase(roots[fx], 1, ranger, p+1, ranger);
segt.modify(roots[fx], 1, ranger, p, log(val), mycnt);
}
int operation_5(int x, int k){
int fx = un.Find(x);
int res = segt.kth(roots[fx], 1, ranger, k);
return DeQuery(res);
}
int operation_6(int a, int b){
int fa = un.Find(a), fb = un.Find(b);
double x1 = segt.tree[roots[fa]].lg;
double x2 = segt.tree[roots[fb]].lg;
return x1 > x2;
}
int main(){
scanf("%d", &m);
for(int i = 1; i <= m; ++i){
int c,x,y = 0;
scanf("%d%d", &c, &x);
if(c != 1 && c !=7){
scanf("%d", &y);
}
if(c == 1){
tmp[++tmp[0]] = x;
++n;
}
if(c == 3 || c == 4){
tmp[++tmp[0]] = y;
}
inputs[i] = input(c, x, y);
}
un.init(n);
std::sort(tmp+1, tmp+1+tmp[0]);
tmp[0] = std::unique(tmp+1, tmp+1+tmp[0])-tmp-1;
ranger = tmp[0];
int ptscnt = 0;
for(int i = 1; i <= m; ++i){
int opt = inputs[i].opt;
int x = inputs[i].x, y = inputs[i].y;
switch(opt){
case 1:
++ptscnt;
segt.modify(roots[ptscnt], 1, ranger, Query(x), log(x), 1);
break;
case 2:
un.merge(x, y);
break;
case 3:{
operation_3(x, y);
break;
}
case 4:
operation_4(x, y);
break;
case 5:{
int res = operation_5(x, y);
printf("%d\n", res);
break;
}
case 6:{
int res = operation_6(x, y);
printf("%d\n", res);
break;
}
case 7:{
int ans = un.getsiz(x);
printf("%d\n", ans);
break;
}
}
}
return 0;
}
T3
#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn = 200000+10, maxtr = 32*maxn, maxm = 2*maxn;
int n;
int v[maxn], tmp[maxn];
int roots[maxn];
int len;
struct segment_tree{
struct node{
int ls, rs, val, lazy;
}tree[maxtr];
int tot;
segment_tree(){
tot = 0;
}
inline int newnode(){
return ++tot;
}
inline void update(int p, int val){
tree[p].val += val;
tree[p].lazy += val;
}
inline void push_down(int p){
int ls = tree[p].ls, rs = tree[p].rs;
if(ls)update(ls, tree[p].lazy);
if(rs)update(rs, tree[p].lazy);
tree[p].lazy = 0;
}
void merge(int &rt, int p, int l, int r, int ladd, int radd){
// printf("MERGE %d %d %d %d %d %d\n",rt, p, l, r, ladd, radd);
ladd = std::max(ladd, tree[rt].val), radd = std::max(radd, tree[p].val);
if(!rt || !p){
if(rt) update(rt, radd);//這里相當與單點merge的遞回到了葉子，這里是遞回到了區間，
if(p) update(p, ladd), rt = p;//加上另外的子樹的影響
//不知道y這里有沒有用
return;
}
push_down(rt);
push_down(p);
int mid = (l+r)>>1;
merge(tree[rt].ls, tree[p].ls, l, mid, ladd, radd);
merge(tree[rt].rs, tree[p].rs, mid+1, r, ladd, radd);
tree[rt].val = ladd+radd;
}
int query(int p, int l, int r, int s){//單點查詢
if(!p) return 0;
if(l == r) return tree[p].val;
int mid = (l+r)>>1;
int ret = tree[p].val;//懶惰標記永久化
push_down(p);
if(s <= mid)
ret = std::max(ret, query(tree[p].ls, l, mid, s));
else
ret = std::max(ret, query(tree[p].rs, mid+1, r , s));
return ret;
}
void modify(int &p, int l, int r, int s, int t, int val){
//區間取最大值
if(!p) p = ++tot;
// printf("Modify %d %d %d %d %d %d\n", p, l, r, s ,t, val);
if(s <= l && r <= t){
tree[p].val = std::max(tree[p].val, val);
return;
}
int mid = (l+r)>>1;
push_down(p);
if(s <= mid)
modify(tree[p].ls, l, mid, s, t, val);
if(t > mid)
modify(tree[p].rs, mid+1, r ,s ,t ,val);
}
}segt;
struct Graph{
struct edge{
int to, nxt;
edge(){}
edge(int a, int b):to(a), nxt(b){}
}e[maxm];
int head[maxn];
inline void ins(int frm, int to){
static int i = 0;
++i;
e[i] = edge(to, head[frm]);
head[frm] = i;
}
void dfs(int u, int fa){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
dfs(v, u);
segt.merge(roots[u], roots[v], 1, len, 0, 0);
}
segt.modify(roots[u], 1, len, v[u], len, segt.query(roots[u], 1, len, v[u]-1)+1);
// printf("ROOT %d = %d\n", u, roots[u]);
}
}G;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
int x;
scanf("%d%d", v+i, &x);
if(x == 0) continue;
G.ins(i, x);
G.ins(x, i);
}
memcpy(tmp, v, sizeof v);
std::sort(tmp+1, tmp+1+n);
len = std::unique(tmp+1, tmp+1+n)-tmp-1;
for(int i = 1; i <= n; ++i)
v[i] = std::lower_bound(tmp+1, tmp+len+1, v[i])-tmp;
G.dfs(1, 1);
printf("%d\n", segt.query(roots[1], 1, len, len));
return 0;
}
T4
#include<cstdio>
#include<cassert>
#include<algorithm>
const int maxn = 1e5+10, maxm = 2*maxn, maxtr = 50*maxn, maxz = 1e5+5, INF = 0x3f3f3f3f;
struct max_node{
int p, val;
max_node(){p = 0, val = 0;}
max_node(int a, int b):p(a), val(b){}
bool operator <(const max_node& rhs)const{
if(val == rhs.val)
return p > rhs.p;
return val < rhs.val;
}
};
int roots[maxn];
struct Graph{
struct edge{
int to, nxt;
edge(){}
edge(int a, int b):to(a), nxt(b){}
}e[maxm];
int head[maxn];
int dep[maxn], siz[maxn], son[maxn], top[maxn], fas[maxn];
void ins(int u, int v){
static int i = 0;
++i;
e[i] = edge(v, head[u]);
head[u] = i;
}
void dfs1(int u){
siz[u] = 1;
dep[u] = dep[fas[u]]+1;
for(int i = head[u];i;i=e[i].nxt){
int v = e[i].to;
if(v == fas[u]) continue;
fas[v] = u;
dfs1(v);
if(!son[u] || siz[son[u]] < siz[v]){
son[u] = v;
}
siz[u] += siz[v];
}
}
void dfs2(int u, int tp){
top[u] = tp;
if(son[u])
dfs2(son[u], tp);
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fas[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int getlca(int u, int v){
while(top[u] != top[v]){
if(dep[top[u]] > dep[top[v]]) u = fas[top[u]];
else v = fas[top[v]];
}
return dep[u] < dep[v] ? u : v;
}
}G;
struct segt{
struct node{
int ls, rs, val;
max_node key;
node(){}
}tree[maxtr];
int tot;
segt(){tot = 0;}
int newnode(){
return ++tot;
}
void push_up(int p){
int lch = tree[p].ls, rch = tree[p].rs;
tree[p].val = tree[lch].val+tree[rch].val;
tree[p].key = std::max(tree[lch].key, tree[rch].key);
}
void update(int p, int val, int s){
tree[p].val += val;
tree[p].key = max_node(s, tree[p].val);
//不能被負數的救濟糧拐跑
}
void modify(int &p, int l, int r, int s, int val){
if(!p) p = newnode();
// printf("Modify %d in %d %d at %d val %d key %d %d \n", p, l, r, s, val, tree[p].key.p, tree[p].key.val);
if(l == r){
// printf("RET %d in %d %d at %d val %d key %d %d\n", p, l, r, s , val, tree[p].key.p ,tree[p].key.val);
return update(p, val, s);
}
int mid = (l+r)>>1;
if(s <= mid)
modify(tree[p].ls, l, mid, s, val);
else
modify(tree[p].rs, mid+1, r, s, val);
push_up(p);
// printf("Modify pushup %d val %d key %d %d\n", p,tree[p].val, tree[p].key.val, tree[p].key.p);
}
int Query(int p){
return tree[p].key.p;
}
void merge(int &rt, int p, int l, int r){
// printf("MERGE %d FROM %d IN %d %d\n", rt, p, l, r);
if(!p) return;
if(!rt) return rt = p, void();
if(l == r){
assert(l == r);
update(rt, tree[p].val, l);
return;
}
int mid = (l+r)>>1;
merge(tree[rt].ls, tree[p].ls, l, mid);
merge(tree[rt].rs, tree[p].rs, mid+1, r);
push_up(rt);
// printf("Merge pushup %d val %d key %d %d\n", p,tree[p].val, tree[p].key.val, tree[p].key.p);
}
}segt;
int n, m;
int ans[maxn];
void dfs(int u, int fa){
for(int i = G.head[u];i;i=G.e[i].nxt){
int v = G.e[i].to;
if(v == fa) continue;
dfs(v, u);
segt.merge(roots[u], roots[v], 1, maxz);
}
// printf("%d %d\n", u, roots[u]);
ans[u] = segt.Query(roots[u]);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n-1; ++i){
int u,v;
scanf("%d%d", &u, &v);
G.ins(u,v);
G.ins(v,u);
}
G.dfs1(1);
G.dfs2(1, 1);
/*
for(int i = 1; i <= n; ++i){
for(int j = 1 ; j <= n; ++j){
if(i == j) continue;
printf("%d %d %d\n", i, j, G.getlca(i, j));
}
}*/
for(int i = 1; i <= m; ++i){
int x,y,z;
scanf("%d%d%d", &x, &y, &z);
int mylca = G.getlca(x, y), falca = G.fas[mylca];
segt.modify(roots[x], 1, maxz, z, 1);
segt.modify(roots[y], 1, maxz, z, 1);
segt.modify(roots[mylca], 1, maxz, z, -1);
// printf("add %d %d %d %d\n", x, y, mylca, falca);
if(falca)segt.modify(roots[falca], 1, maxz, z, -1);
}
dfs(1, 0);
for(int i = 1; i <= n; ++i){
printf("%d\n", ans[i]);
}
return 0;
}
T5
#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn = 200000+10, maxtr = 32*maxn, maxm = 2*maxn;
int n;
int v[maxn], tmp[maxn];
int roots[maxn];
int len;
struct segment_tree{
struct node{
int ls, rs, val, lazy;
}tree[maxtr];
int tot;
segment_tree(){
tot = 0;
}
int newnode(){
return ++tot;
}
void update(int p, int val){
tree[p].val += val;
tree[p].lazy += val;
}
void push_down(int p){
int ls = tree[p].ls, rs = tree[p].rs;
if(ls)update(ls, tree[p].lazy);
if(rs)update(rs, tree[p].lazy);
tree[p].lazy = 0;
}
void merge(int &rt, int p, int l, int r, int ladd, int radd){
// printf("MERGE %d %d %d %d %d %d\n",rt, p, l, r, ladd, radd);
ladd = std::max(ladd, tree[rt].val), radd = std::max(radd, tree[p].val);
if(!rt || !p){
if(rt) update(rt, radd);//這里相當與單點merge的遞回到了葉子，這里是遞回到了區間，
if(p) update(p, ladd), rt = p;//加上另外的子樹的影響
//不知道y這里有沒有用
return;
}
push_down(rt);
push_down(p);
int mid = (l+r)>>1;
merge(tree[rt].ls, tree[p].ls, l, mid, ladd, radd);
merge(tree[rt].rs, tree[p].rs, mid+1, r, ladd, radd);
tree[rt].val = ladd+radd;
}
int query(int p, int l, int r, int s){//單點查詢
if(!p) return 0;
if(l == r) return tree[p].val;
int mid = (l+r)>>1;
int ret = tree[p].val;//懶惰標記永久化
push_down(p);
if(s <= mid)
ret = std::max(ret, query(tree[p].ls, l, mid, s));
else
ret = std::max(ret, query(tree[p].rs, mid+1, r , s));
return ret;
}
void modify(int &p, int l, int r, int s, int t, int val){
//區間取最大值
if(!p) p = newnode();
// printf("Modify %d %d %d %d %d %d\n", p, l, r, s ,t, val);
if(s <= l && r <= t){
tree[p].val = std::max(tree[p].val, val);
return;
}
int mid = (l+r)>>1;
push_down(p);
if(s <= mid)
modify(tree[p].ls, l, mid, s, t, val);
if(t > mid)
modify(tree[p].rs, mid+1, r ,s ,t ,val);
}
}segt;
struct Graph{
struct edge{
int to, nxt;
edge(){}
edge(int a, int b):to(a), nxt(b){}
}e[maxm];
int head[maxn];
void ins(int frm, int to){
static int i = 0;
++i;
e[i] = edge(to, head[frm]);
head[frm] = i;
}
void dfs(int u, int fa){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
dfs(v, u);
segt.merge(roots[u], roots[v], 1, len, 0, 0);
}
segt.modify(roots[u], 1, len, 1, v[u], segt.query(roots[u], 1, len, v[u])+1);
// printf("ROOT %d = %d\n", u, roots[u]);
}
}G;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d", v+i);
}
for(int i = 2; i <= n; ++i){
int x;
scanf("%d", &x);
G.ins(i, x);
G.ins(x, i);
}
memcpy(tmp, v, sizeof v);
std::sort(tmp+1, tmp+1+n);
len = std::unique(tmp+1, tmp+1+n)-tmp-1;
for(int i = 1; i <= n; ++i)
v[i] = std::lower_bound(tmp+1, tmp+len+1, v[i])-tmp;
G.dfs(1, 1);
printf("%d\n", segt.query(roots[1], 1, len, 1));
return 0;
}
T5
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int maxn = 1e5+10, maxe = 2*maxn, maxtr = 32*maxn, maxq = maxn;
int siz[maxn];
int roots[maxn];
int n, q;
struct Graph{
struct edge{
int to, nxt;
edge(){}
edge(int a, int b):to(a), nxt(b){}
}e[maxe];
int head[maxn];
void ins(int frm, int to){
static int i = 0;
++i;
e[i] = edge(to, head[frm]);
head[frm] = i;
}
int dfn[maxn], tim;
void dfs(int u){
//printf("%d", u);
siz[u] = 1;
dfn[u] = ++tim;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(dfn[v]) continue;
dfs(v);
siz[u] += siz[v];
}
}
void graph_prework(){
for(int i = 1; i <= n; ++i){
if(!dfn[i]){
dfs(i);
}
}
}
}G;
struct segt{
struct node{
int ls, rs, val;
node(){}
}tree[maxtr];
int tot;
segt(){
tot = 0;
}
void push_up(int rt){
tree[rt].val = tree[tree[rt].ls].val + tree[tree[rt].rs].val;
}
int newnode(){
return ++tot;
}
void update(int p, int val){
tree[p].val += val;
}
void modify(int &rt, int l, int r, int s){
if(!rt) rt = newnode();
if(l == r){
return update(rt, 1);
}
int mid = (l+r)>>1;
if(s <= mid)
modify(tree[rt].ls, l, mid, s);
else
modify(tree[rt].rs, mid+1, r, s);
push_up(rt);
}
int query(int rt, int l, int r, int s,int t){
if(!rt) return 0;
if(s <= l && r <= t){
return tree[rt].val;
}
int mid = (l+r)>>1;
int ans = 0;
if(s <= mid)
ans = query(tree[rt].ls, l, mid, s, t);
if(t > mid)
ans += query(tree[rt].rs, mid+1, r, s, t);
return ans;
}
void merge(int &rt, int p, int l, int r){
//printf("MERGE %d %d %d %d\n", rt, p, l, r);
if(!p) return;
if(!rt) return rt = p, void();
if(l == r){
return update(rt, tree[p].val);
//好像直接+1就行
}
int mid = (l+r)>>1;
merge(tree[rt].ls, tree[p].ls, l, mid);
merge(tree[rt].rs, tree[p].rs, mid+1, r);
push_up(rt);
}
}segt;
struct input_t{
int opt, x, y;
input_t(){}
input_t(int a, int b, int c):opt(a), x(b), y(c){}
}inputs[maxq];
struct DSU{
int fa[maxn];
int sizun[maxn];//聯通塊的大小
void init(int len){
for(int i = 1; i <= len; ++i){
fa[i] = i;
sizun[i] = 1;
}
}
int find(int x){
return x == fa[x]?x:fa[x] = find(fa[x]);
}
void merge(int x, int y){
int fx = find(x), fy = find(y);
int &sx = sizun[fx], &sy = sizun[fy];
fa[fy] = fx;
sizun[fx] += sy;
/*
if(sx >= sy){
sizun[fx] += sy;
fa[fy] = fx;
}else{
sizun[fy] += sx;
fa[fx] = fy;
}*/
}
int getsiz(int x){
return sizun[find(x)];
}
}un;
int main(){
scanf("%d%d", &n, &q);
for(int i = 1; i <= q; ++i){
int x, y;
char opt;
scanf(" %c%d%d", &opt, &x, &y);
opt = opt == 'A'?1:2;
inputs[i] = input_t(opt, x, y);
if(opt == 1)
{
G.ins(x, y);
G.ins(y, x);
}
}
G.graph_prework();
un.init(n);
/*
for(int i = 1; i <= n; ++i){
printf("%d ", siz[i]);
}
puts("");
for(int i = 1 ; i<= n; ++i){
printf("%d ", G.dfn[i]);
}
puts("");
*/
for(int i = 1; i <= n; ++i){
segt.modify(roots[i], 1, n, G.dfn[i]);
}
for(int i = 1; i <= q; ++i){
int opt = inputs[i].opt, x = inputs[i].x, y = inputs[i].y;
if(G.dfn[x] > G.dfn[y]) std::swap(x, y);
//x是y的父親
if(opt == 1){
//printf("MERGE %d %d\n", x, y);
segt.merge(roots[un.find(x)], roots[un.find(y)], 1, n);
roots[y] = roots[x];
un.merge(x, y);
}else{
ll sizsub = segt.query(roots[un.find(y)], 1, n, G.dfn[y], G.dfn[y]+siz[y]-1), sizall = un.getsiz(x);
ll ans = sizsub*(sizall-sizsub);
//printf("l r %d %d x y %d %d sub %lld all %lld\n", G.dfn[y],G.dfn[y]+siz[y]-1, x, y, sizsub, sizall);
printf("%lld\n", ans);
}
}
return 0;
}
T6
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int maxn = 1e5+10, maxe = 2*maxn, maxtr = 32*maxn, maxq = maxn;
int siz[maxn];
int roots[maxn];
int n, q;
struct Graph{
struct edge{
int to, nxt;
edge(){}
edge(int a, int b):to(a), nxt(b){}
}e[maxe];
int head[maxn];
void ins(int frm, int to){
static int i = 0;
++i;
e[i] = edge(to, head[frm]);
head[frm] = i;
}
int dfn[maxn], tim;
void dfs(int u){
//printf("%d", u);
siz[u] = 1;
dfn[u] = ++tim;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(dfn[v]) continue;
dfs(v);
siz[u] += siz[v];
}
}
void graph_prework(){
for(int i = 1; i <= n; ++i){
if(!dfn[i]){
dfs(i);
}
}
}
}G;
struct segt{
struct node{
int ls, rs, val;
node(){}
}tree[maxtr];
int tot;
segt(){
tot = 0;
}
void push_up(int rt){
tree[rt].val = tree[tree[rt].ls].val + tree[tree[rt].rs].val;
}
int newnode(){
return ++tot;
}
void update(int p, int val){
tree[p].val += val;
}
void modify(int &rt, int l, int r, int s){
if(!rt) rt = newnode();
if(l == r){
return update(rt, 1);
}
int mid = (l+r)>>1;
if(s <= mid)
modify(tree[rt].ls, l, mid, s);
else
modify(tree[rt].rs, mid+1, r, s);
push_up(rt);
}
int query(int rt, int l, int r, int s,int t){
if(!rt) return 0;
if(s <= l && r <= t){
return tree[rt].val;
}
int mid = (l+r)>>1;
int ans = 0;
if(s <= mid)
ans = query(tree[rt].ls, l, mid, s, t);
if(t > mid)
ans += query(tree[rt].rs, mid+1, r, s, t);
return ans;
}
void merge(int &rt, int p, int l, int r){
//printf("MERGE %d %d %d %d\n", rt, p, l, r);
if(!p) return;
if(!rt) return rt = p, void();
if(l == r){
return update(rt, tree[p].val);
//好像直接+1就行
}
int mid = (l+r)>>1;
merge(tree[rt].ls, tree[p].ls, l, mid);
merge(tree[rt].rs, tree[p].rs, mid+1, r);
push_up(rt);
}
}segt;
struct input_t{
int opt, x, y;
input_t(){}
input_t(int a, int b, int c):opt(a), x(b), y(c){}
}inputs[maxq];
struct DSU{
int fa[maxn];
int sizun[maxn];//聯通塊的大小
void init(int len){
for(int i = 1; i <= len; ++i){
fa[i] = i;
sizun[i] = 1;
}
}
int find(int x){
return x == fa[x]?x:fa[x] = find(fa[x]);
}
void merge(int x, int y){
int fx = find(x), fy = find(y);
int &sx = sizun[fx], &sy = sizun[fy];
fa[fy] = fx;
sizun[fx] += sy;
/*
if(sx >= sy){
sizun[fx] += sy;
fa[fy] = fx;
}else{
sizun[fy] += sx;
fa[fx] = fy;
}*/
}
int getsiz(int x){
return sizun[find(x)];
}
}un;
int main(){
scanf("%d%d", &n, &q);
for(int i = 1; i <= q; ++i){
int x, y;
char opt;
scanf(" %c%d%d", &opt, &x, &y);
opt = opt == 'A'?1:2;
inputs[i] = input_t(opt, x, y);
if(opt == 1)
{
G.ins(x, y);
G.ins(y, x);
}
}
G.graph_prework();
un.init(n);
/*
for(int i = 1; i <= n; ++i){
printf("%d ", siz[i]);
}
puts("");
for(int i = 1 ; i<= n; ++i){
printf("%d ", G.dfn[i]);
}
puts("");
*/
for(int i = 1; i <= n; ++i){
segt.modify(roots[i], 1, n, G.dfn[i]);
}
for(int i = 1; i <= q; ++i){
int opt = inputs[i].opt, x = inputs[i].x, y = inputs[i].y;
if(G.dfn[x] > G.dfn[y]) std::swap(x, y);
//x是y的父親
if(opt == 1){
//printf("MERGE %d %d\n", x, y);
segt.merge(roots[un.find(x)], roots[un.find(y)], 1, n);
roots[y] = roots[x];
un.merge(x, y);
}else{
ll sizsub = segt.query(roots[un.find(y)], 1, n, G.dfn[y], G.dfn[y]+siz[y]-1), sizall = un.getsiz(x);
ll ans = sizsub*(sizall-sizsub);
//printf("l r %d %d x y %d %d sub %lld all %lld\n", G.dfn[y],G.dfn[y]+siz[y]-1, x, y, sizsub, sizall);
printf("%lld\n", ans);
}
}
for(int i = 5; i <= 9; ++i){
//printf("SIZ = %d\n", segt.query(roots[9], 1, n, i, i));
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296228.html
標籤：其他
上一篇：動態規劃