首页 > 代码库 > Partition(线段树的离线处理）

Partition(线段树的离线处理）

2024-07-06 22:13:13   225人阅读

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

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

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

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

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

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

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 #include<map>
 11 using namespace std;
 12 #define N 100010
 13 #define LL long long
 14 #define INF 0xfffffff
 15 const double eps = 1e-8;
 16 const double pi = acos(-1.0);
 17 const double inf = ~0u>>2;
 18 #pragma comment(linker, "/STACK:1024000000,1024000000")
 19 int s[N<<2][2],a[N<<1],b[N];
 20 map<int,int>f;
 21 vector<int>ed[N];//儿子
 22 vector<int>dd[N];//以i节点结束的询问
 23 int g ;
 24 struct node{
 25     int v,x;
 26     int ax,ay,f;
 27 }p[N];
 28 void up(int w)
 29 {
 30     s[w][0] = s[w<<1][0]+s[w<<1|1][0];//向左走
 31     s[w][1] = s[w<<1][1]+s[w<<1|1][1];//向右走
 32 }
 33 void build(int l,int r,int w)
 34 {
 35     if(l==r)
 36     {
 37         s[w][0] = s[w][1] = 0;
 38         return ;
 39     }
 40     int m = (l+r)>>1;
 41     build(l,m,w<<1);
 42     build(m+1,r,w<<1|1);
 43     up(w);
 44 }
 45 void update(int p,int d,int dir,int l,int r,int w)
 46 {
 47     if(l==r)
 48     {
 49         s[w][dir] += d;
 50         return ;
 51     }
 52     int m = (l+r)>>1;
 53     if(p<=m) update(p,d,dir,l,m,w<<1);
 54     else update(p,d,dir,m+1,r,w<<1|1);
 55     up(w);
 56 }
 57 int query(int a,int b,int dir,int l,int r,int w)
 58 {
 59     if(a<=l&&b>=r)
 60     {
 61         return s[w][dir];
 62     }
 63     int m = (l+r)>>1;
 64     int res=0;
 65     if(a<=m) res+=query(a,b,dir,l,m,w<<1);
 66     if(b>m) res+=query(a,b,dir,m+1,r,w<<1|1);
 67     return res;
 68 }
 69 void dfs(int u,int pre)
 70 {
 71     int i;
 72     for(i = 0; i < dd[u].size(); i++)
 73     {
 74         int k = dd[u][i];
 75         int id = f[p[k].x];
 76        // cout<<k<<endl;
 77         int cnt1 = query(id,id,0,1,g,1);
 78         int cnt2 = query(id,id,1,1,g,1);
 79         //cout<<cnt1<<" "<<cnt2<<" "<<u<<" "<<id<<endl;
 80         if(cnt1||cnt2)
 81         {
 82             p[k].f = 0;
 83             continue;
 84         }
 85         else
 86         {
 87             p[k].f = 1;
 88             int l0 = query(1,id,0,1,g,1);
 89             int l1 = query(1,id,1,1,g,1);
 90             int r0 = query(id,g,0,1,g,1);
 91             int r1 = query(id,g,1,1,g,1);
 92            // cout<<l0<<" "<<l1<<" "<<r0<<" "<<r1<<endl;
 93             p[k].ay = r0+r1+3*(l1+l0);
 94             p[k].ax = l1;
 95         }
 96     }
 97     for(i = 0;i < ed[u].size() ; i++)
 98     {
 99         int v = ed[u][i];
100         int id = f[b[u]];
101        // cout<<id<<" "<<u<<endl;
102         if(i==0)
103         {
104             update(id,1,0,1,g,1);
105         }
106         else update(id,1,1,1,g,1);
107         dfs(v,u);
108         if(i==0)
109         update(id,-1,0,1,g,1);
110         else update(id,-1,1,1,g,1);
111     }
112 }
113 int main()
114 {
115     int t,i,n,m,q;
116     cin>>t;
117     while(t--)
118     {
119         scanf("%d",&n);
120         f.clear();
121         g = 0;
122         for(i = 1; i <=n; i++)
123         {
124             scanf("%d",&a[i]);
125             b[i] = a[i];
126             ed[i].clear();
127             dd[i].clear();
128         }
129         scanf("%d",&m);
130         for(i = 1; i <= m; i++)
131         {
132             int u,l,r;
133             scanf("%d%d%d",&u,&l,&r);
134             ed[u].push_back(l);
135             ed[u].push_back(r);
136         }
137         scanf("%d",&q);
138         for(i = 1;i <= q ;i++)
139         {
140             scanf("%d%d",&p[i].v,&p[i].x);
141             dd[p[i].v].push_back(i);
142             a[n+i] = p[i].x;
143         }
144         sort(a+1,a+n+q+1);
145         f[a[1]] = ++g;
146         for(i = 2; i <= n+q ; i++)
147         {
148             if(a[i]!=a[i-1])
149             f[a[i]] = ++g;
150         }
151         build(1,g,1);
152         dfs(1,-1);
153         for(i = 1; i <= q;  i++)
154         {
155             if(p[i].f==0)
156             printf("%d\n",0);
157             else
158             printf("%d %d\n",p[i].ax,p[i].ay);
159         }
160     }
161     return 0;
162 }
View Code

 

 


联系
我们