[做题记录] [Ynoi2011] 成都七中

本来的做法是点分树上暴力找到最靠上的与\(x\)相连的点， 实际上可以从上往下点分治。
然后矩形也不用重新表示， 可以扫右端点， 保存每个颜色最大的左端点就好了。
然后直接写。不得不说这样的话写起来简单多了。

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

class Input {
	#define MX 1000000
	private :
		char buf[MX], *p1 = buf, *p2 = buf;
		inline char gc() {
			if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MX, stdin);
			return p1 == p2 ? EOF : *(p1 ++);
		}
	public :
		Input() {
			#ifdef Open_File
				freopen("a.in", "r", stdin);
				freopen("a.out", "w", stdout);
			#endif
		}
		template <typename T>
		inline Input& operator >>(T &x) {
			x = 0; int f = 1; char a = gc();
			for(; ! isdigit(a); a = gc()) if(a == ‘-‘) f = -1;
			for(; isdigit(a); a = gc()) 
				x = x * 10 + a - ‘0‘;
			x *= f;
			return *this;
		}
		inline Input& operator >>(char &ch) {
			while(1) {
				ch = gc();
				if(ch != ‘\n‘ && ch != ‘ ‘) return *this;
			}
		}
		inline Input& operator >>(char *s) {
			int p = 0;
			while(1) {
				s[p] = gc();
				if(s[p] == ‘\n‘ || s[p] == ‘ ‘ || s[p] == EOF) break;
				p ++; 
			}
			s[p] = ‘\0‘;
			return *this;
		}
	#undef MX
} Fin;

class Output {
	#define MX 1000000
	private :
		char ouf[MX], *p1 = ouf, *p2 = ouf;
		char Of[105], *o1 = Of, *o2 = Of;
		void flush() { fwrite(ouf, 1, p2 - p1, stdout); p2 = p1; }
		inline void pc(char ch) {
			* (p2 ++) = ch;
			if(p2 == p1 + MX) flush();
		}
	public :
		template <typename T> 
		inline Output& operator << (T n) {
			if(n < 0) pc(‘-‘), n = -n;
			if(n == 0) pc(‘0‘);
			while(n) *(o1 ++) = (n % 10) ^ 48, n /= 10;
			while(o1 != o2) pc(* (--o1));
			return *this; 
		}
		inline Output & operator << (char ch) {
			pc(ch); return *this; 
		}
		inline Output & operator <<(const char *ch) {
			const char *p = ch;
			while( *p != ‘\0‘ ) pc(* p ++);
			return * this;
		}
		~Output() { flush(); } 
	#undef MX
} Fout;

#define cin Fin
#define cout Fout
#define endl ‘\n‘

using LL = long long;

inline int log2(unsigned int x);
inline int popcount(unsigned x);
inline int popcount(unsigned long long x);

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;

struct BIT {
	int c[N];
	#define lowbit(x) (x & -x)
	void upd(int x, int y) {
		//x ++;
		for(; x <= n; x += lowbit(x)) c[x] += y;
	}
	int qry(int x) {
		int ans = 0;
		for(; x; x -= lowbit(x)) ans += c[x];
		return ans;
	}
} bit;

struct edge {
	int to, next;
} e[N << 1];

int cnt, head[N], co[N];
void push(int x, int y) {
	e[++ cnt] = (edge) {y, head[x]}; head[x] = cnt;
}

int fa[N];
int all, rt, sz[N], vis[N];
void findrt(int x, int fx) {
	sz[x] = 1;
	int mx = 0;
	for(int i = head[x]; i; i = e[i].next) {
		int y = e[i].to;
		if(y == fx || vis[y]) continue;
		findrt(y, x);
		sz[x] += sz[y];
		mx = max(mx, sz[y]);
	}
	if(mx < all - sz[x]) mx = all - sz[x];
	if(mx * 2 <= all || rt == 0) rt = x;
}

struct Qry {
	int l, r, id;
	Qry() {}
	Qry(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {}
} ;

vector<Qry> vec[N];
int bj[N];

void dfs(int x, int fx, int mnv, int mxv, vector<Qry> & ask, vector<Qry> &qry) {
	ask.push_back(Qry(mnv, mxv, co[x]));
	for(Qry p : vec[x]) if(p.l <= mnv && mxv <= p.r && ! bj[p.id]) bj[p.id] = 1, qry.push_back(p);
	for(int i = head[x]; i; i = e[i].next) {
		int y = e[i].to;
		if(vis[y] || y == fx) continue;
		dfs(y, x, min(mnv, y), max(mxv, y), ask, qry);
	}
}

int mx[N], Ans[N];

void calc(int x) {
	static vector<Qry> ask, qry;
	ask.clear(); qry.clear();
	dfs(x, 0, x, x, ask, qry);
	sort(ask.begin(), ask.end(), [](Qry a, Qry b) { return a.r < b.r; } );
	sort(qry.begin(), qry.end(), [](Qry a, Qry b) { return a.r < b.r; } );
	for(int i = 0, j = 0; i < qry.size(); i ++) {
		while(j < ask.size() && ask[j].r <= qry[i].r) {
			if(ask[j].l > mx[ask[j].id]) {
				if(mx[ask[j].id] != 0) bit.upd(mx[ask[j].id], -1);
				mx[ask[j].id] = ask[j].l, bit.upd(mx[ask[j].id], 1);
			}
			j ++;
		}
		Ans[qry[i].id] = bit.qry(n) - bit.qry(qry[i].l - 1);
	}
	for(Qry p : ask) {
		if(mx[p.id]) bit.upd(mx[p.id], -1);
		mx[p.id] = 0;
	}
}

void solve(int x) {
	vis[x] = 1;
	//cerr << x << endl;
	calc(x);
	for(int i = head[x]; i; i = e[i].next) {
		int y = e[i].to;
		if(vis[y]) continue;
		findrt(y, 0);
		rt = 0; all = sz[y];
		findrt(y, 0);
		solve(rt);
	}
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> co[i];
	for(int i = 2, x, y; i <= n; i ++) {
		cin >> x >> y; 
		push(x, y); push(y, x);
	}
	for(int i = 1; i <= m; i ++) {
		int l, r, x;
		cin >> l >> r >> x;
		vec[x].push_back( Qry(l, r, i) );
	}
	all = n;
	findrt(1, 0);
	findrt(rt, 0);
	solve(rt);
	for(int i = 1; i <= m; i ++) cout << Ans[i] << endl;
	return 0;
}

inline int log2(unsigned int x) { return __builtin_ffs(x); }
inline int popcount(unsigned int x) { return __builtin_popcount(x); }
inline int popcount(unsigned long long x) { return __builtin_popcountl(x); }

// Last Year

[做题记录] [Ynoi2011] 成都七中

原文：https://www.cnblogs.com/clover4/p/15265388.html