Partition(线段树的离线处理）

有一点类似区间K值的求法。

这里有两颗树，一个是自己建的线段树，一个是题目中给定的树。以线段树和树进行区分。

首先离散化一下，以离散化后的结果建线段树，线段树的节点开了2维，一维保存当前以当前节点为权值的树的节点是往左走的，另一维是往右走的，用一个vector保存一下以当前i节点为结束的询问，因为所有的询问都是从根节点出发的，只需保存终点即可。

然后从根节点出发遍历整棵树，当走到当前节点时，枚举以当前节点的询问q[i]，然后求出比q[i].x大的向左和向右走的节点个数，以及比它小的个数，如果有相等的直接为0，最后根据可能性加起来即可。

每走完一个节点，回退时，把当前节点更新为未走。

把树节点的权值跟询问的搞混了，WA一次。。搞了组数据才看出来

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 int s[N<<][],a[N<<],b[N];

 map<int,int>f;

 vector<int>ed[N];//儿子

 vector<int>dd[N];//以i节点结束的询问

 int g ;

 struct node{

     int v,x;

     int ax,ay,f;

 }p[N];

 void up(int w)

 {

     s[w][] = s[w<<][]+s[w<<|][];//向左走

     s[w][] = s[w<<][]+s[w<<|][];//向右走

 }

 void build(int l,int r,int w)

 {

     if(l==r)

     {

         s[w][] = s[w][] = ;

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<);

     build(m+,r,w<<|);

     up(w);

 }

 void update(int p,int d,int dir,int l,int r,int w)

 {

     if(l==r)

     {

         s[w][dir] += d;

         return ;

     }

     int m = (l+r)>>;

     if(p<=m) update(p,d,dir,l,m,w<<);

     else update(p,d,dir,m+,r,w<<|);

     up(w);

 }

 int query(int a,int b,int dir,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         return s[w][dir];

     }

     int m = (l+r)>>;

     int res=;

     if(a<=m) res+=query(a,b,dir,l,m,w<<);

     if(b>m) res+=query(a,b,dir,m+,r,w<<|);

     return res;

 }

 void dfs(int u,int pre)

 {

     int i;

     for(i = ; i < dd[u].size(); i++)

     {

         int k = dd[u][i];

         int id = f[p[k].x];

        // cout<<k<<endl;

         int cnt1 = query(id,id,,,g,);

         int cnt2 = query(id,id,,,g,);

         //cout<<cnt1<<" "<<cnt2<<" "<<u<<" "<<id<<endl;

         if(cnt1||cnt2)

         {

             p[k].f = ;

             continue;

         }

         else

         {

             p[k].f = ;

             int l0 = query(,id,,,g,);

             int l1 = query(,id,,,g,);

             int r0 = query(id,g,,,g,);

             int r1 = query(id,g,,,g,);

            // cout<<l0<<" "<<l1<<" "<<r0<<" "<<r1<<endl;

             p[k].ay = r0+r1+*(l1+l0);

             p[k].ax = l1;

         }

     }

     for(i = ;i < ed[u].size() ; i++)

     {

         int v = ed[u][i];

         int id = f[b[u]];

        // cout<<id<<" "<<u<<endl;

         if(i==)

         {

             update(id,,,,g,);

         }

         else update(id,,,,g,);

         dfs(v,u);

         if(i==)

         update(id,-,,,g,);

         else update(id,-,,,g,);

     }

 }

 int main()

 {

     int t,i,n,m,q;

     cin>>t;

     while(t--)

     {

         scanf("%d",&n);

         f.clear();

         g = ;

         for(i = ; i <=n; i++)

         {

             scanf("%d",&a[i]);

             b[i] = a[i];

             ed[i].clear();

             dd[i].clear();

         }

         scanf("%d",&m);

         for(i = ; i <= m; i++)

         {

             int u,l,r;

             scanf("%d%d%d",&u,&l,&r);

             ed[u].push_back(l);

             ed[u].push_back(r);

         }

         scanf("%d",&q);

         for(i = ;i <= q ;i++)

         {

             scanf("%d%d",&p[i].v,&p[i].x);

             dd[p[i].v].push_back(i);

             a[n+i] = p[i].x;

         }

         sort(a+,a+n+q+);

         f[a[]] = ++g;

         for(i = ; i <= n+q ; i++)

         {

             if(a[i]!=a[i-])

             f[a[i]] = ++g;

         }

         build(,g,);

         dfs(,-);

         for(i = ; i <= q;  i++)

         {

             if(p[i].f==)

             printf("%d\n",);

             else

             printf("%d %d\n",p[i].ax,p[i].ay);

         }

     }

     return ;

 }

巴特西

Partition(线段树的离线处理）

最新文章

热门文章