題意：給一棵樹，點有顏色，$q$ 次詢問，每次給定 $l,r,x$ ，求只保留編號在 $[l,r]$ 中的點時點 $x$ 所在連通塊的顏色數。

所有數 $\le 10^5$

題目背景好評

首先所有顏色不同的話就是數連通塊大小，先想想這個怎么做。

然后不會做，拜拜了您嘞

---

考察所求的 $x$ 所在連通塊在點分治中的過程，這個連通塊一直是完整的直到一個分治中心踩到了這個連通塊中的一個點。建出點分樹后，我們預處理每個點 與所有點分樹上的祖先在原樹上的路徑經過的點編號的最小值與最大值，然后每個詢問把 $x$ 暴力跳祖先就可以找到這個點。

這個點點分樹上的子樹的點包含了所求的連通塊，且這個點在連通塊內。對于子樹內的點，它在連通塊內當且僅當到子樹的根的路徑的編號范圍被詢問區間完全包含。所以對每個點 dfs 一遍子樹，然后就是喜聞樂見的主對角線矩形數顏色問題。

把詢問離線（這道題里面本來就是離線的）掛在右端點上，然后移動右端點，維護每種顏色的點的左端點的最大值，樹狀數組上加一下就可以了。

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <algorithm> #define MAXN 100005 using namespace std; const int INF=0x7fffffff; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } int col[MAXN]; struct node{int l,r,val;}; //ancestor: val=the index of the ancestor //son: val=the color of the son //query: val=the index of the query vector<int> e[MAXN]; vector<node> p[MAXN],s[MAXN],q[MAXN]; int rt,siz[MAXN],maxp[MAXN],vis[MAXN]; void findrt(int u,int f,int sum) {siz[u]=1,maxp[u]=0;for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]&&e[u][i]!=f){findrt(e[u][i],u,sum);siz[u]+=siz[e[u][i]];maxp[u]=max(maxp[u],siz[e[u][i]]);}maxp[u]=max(maxp[u],sum-siz[u]);if (maxp[u]<maxp[rt]) rt=u; } void dfs(int u,int f,int l,int r) {p[u].push_back((node){l,r,rt});s[rt].push_back((node){l,r,col[u]});siz[u]=1;for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]&&e[u][i]!=f){dfs(e[u][i],u,min(l,e[u][i]),max(r,e[u][i]));siz[u]+=siz[e[u][i]];} } void build() {vis[rt]=1;dfs(rt,0,rt,rt);int u=rt;for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]){rt=0,findrt(e[u][i],0,siz[e[u][i]]);build();} } const int N=1e5; struct BIT {int s[MAXN];inline int lowbit(const int& x){return x&-x;}inline void modify(int x,int v){for (;x<=N;s[x]+=v,x+=lowbit(x));}inline int query(int x,int ans=0){for (;x;ans+=s[x],x-=lowbit(x));return ans;} }bit; int mx[MAXN]; vector<node> tf[MAXN],tq[MAXN]; vector<int> lis; int ans[MAXN]; int main() {maxp[0]=INF;int n,m;n=read(),m=read();for (int i=1;i<=n;i++) col[i]=read();for (int i=1;i<n;i++) {int u,v;u=read(),v=read();e[u].push_back(v),e[v].push_back(u);}findrt(1,0,n),build();for (int T=1;T<=m;T++){int l,r,x;l=read(),r=read(),x=read();for (int i=0;i<(int)p[x].size();i++)if (l<=p[x][i].l&&p[x][i].r<=r){q[p[x][i].val].push_back((node){l,r,T});break;}}for (int u=1;u<=n;u++){lis.clear();for (int i=0;i<(int)s[u].size();i++)tf[s[u][i].r].push_back(s[u][i]),lis.push_back(s[u][i].r);for (int i=0;i<(int)q[u].size();i++)tq[q[u][i].r].push_back(q[u][i]),lis.push_back(q[u][i].r);sort(lis.begin(),lis.end());lis.erase(unique(lis.begin(),lis.end()),lis.end());for (int t=0;t<(int)lis.size();t++){int r=lis[t];for (int i=0;i<(int)tf[r].size();i++)if (tf[r][i].l>mx[tf[r][i].val]){if (mx[tf[r][i].val]) bit.modify(mx[tf[r][i].val],-1);bit.modify(mx[tf[r][i].val]=tf[r][i].l,1);}for (int i=0;i<(int)tq[r].size();i++)ans[tq[r][i].val]=bit.query(r)-bit.query(tq[r][i].l-1);}for (int i=0;i<(int)s[u].size();i++){if (mx[s[u][i].val]) bit.modify(mx[s[u][i].val],-1);mx[s[u][i].val]=0;}for (int i=0;i<(int)lis.size();i++) tf[lis[i]].clear(),tq[lis[i]].clear();}for (int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的【Ynoi2011】成都七中【树论】【点分树】【离线】【树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。