icekingdom(2018.10.17)

一句话题意：给你一颗n个点的树，节点初始状态下都是白色，有q次修改，每次修改会把[li,ri]区间内的点染成黑色，并且问黑色点能形成几个联通块，然后会将所有点染回白色。（也就是说每次都只有[li,ri]这个区间内的节点是黑色的）

数据范围：

对于 30%的数据：n<=100,q<=100；

对于 50%的数据：n<=2,000,q<=2,000；

对于 100%的数据：n<=200,000，q<=200,000,对于所有的区间，li<=ri。

30分做法：这个做法几乎没人写吧，两两判断区间内的点是否连通，时间复杂度\(O(n^3)\)

50分做法：题解说的用并查集维护可以做到\(O(n^2)\),蒟蒻表示不费，只能用大水漫灌法，同样\(O(n^2)\)

100分做法：一个很显然的性质，只要区间内任意两点每有一条边相连，联通块个数就少一个，设[l,r]内有k条边相连，答案即为\((r-l+1-k)\)

两种，表示考场上我都想到了，但是都不会写

第一种：裸的二位偏序问题，离线排序然后树状数组维护就好了，考场上我是真没看出这是二位偏序，我也确实对二位偏序理解不深，时间复杂度\(O(nlogn)\)

第二种：在线做法，由上面的性质可知，我们只需要维护每个区间内有多少条边就可以了，我们将所有的树边按照编号较⼩的点从⼩到⼤排序，然后⽤右端点建⼀个可持久化权值线段树，这样对于每个询问，我们只要在li~ri的线段树中查询⽐ri⼩的数有多少个就⾏了，时间复杂度\(O(nlogn)\)，常数略大

以下是第一种做法的代码：

#include<cstdio>

#include<algorithm>

#define lowbit(i) (i&(-i))

struct oo{int x,y,id;}s[400001];

int n,q,sum,f[200001],ans[200001];bool cmp(oo a,oo b){return a.y==b.y?a.id<b.id:a.y<b.y;}

void add(int x){for(int i=x;i<=n;i+=lowbit(i))f[i]++;}

int get(int x){int now=0;for(int i=x;i;i-=lowbit(i))now+=f[i];return now;}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);if(x>y)std::swap(x,y);s[++sum]=(oo){x,y,0};}

    for(int i=1;i<=q;i++)sum++,scanf("%d%d",&s[sum].x,&s[sum].y),s[sum].id=i;

    std::sort(s+1,s+sum+1,cmp);

    for(int i=1;i<=sum;i++)if(s[i].id)ans[s[i].id]=s[i].y-s[i].x+1-get(s[i].y)+get(s[i].x-1);else add(s[i].x);

    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);

}

巴特西

icekingdom(2018.10.17)

最新文章

热门文章