bzoj1146整体二分+树链剖分+树状数组
2018-06-17 23:29:19来源:未知 阅读 ()
其实也没啥好说的
用树状数组可以O(logn)的查询
套一层整体二分就可以做到O(nlngn)
最后用树链剖分让序列上树
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 inline int read() 7 { 8 int x=0,f=1,ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 11 return x*f; 12 } 13 int n,q; 14 int data[80005]; 15 inline void add(int x,int i) 16 { 17 while(x<=n) 18 { 19 data[x]+=i; 20 x+=x&(-x); 21 } 22 } 23 inline int query(int x) 24 { 25 int res=0; 26 while(x>=1) 27 { 28 res+=data[x]; 29 x-=x&(-x); 30 } 31 return res; 32 } 33 int h[80005],next[160005],to[160005],cnt; 34 inline void addedge(int x,int y) 35 { 36 next[cnt]=h[x]; 37 to[cnt]=y; 38 h[x]=cnt; 39 cnt++; 40 } 41 int size[80005],hson[80005],dep[80005],f[80005]; 42 inline void bfs(int x,int fa) 43 { 44 int i; 45 size[x]=1; 46 for(i=h[x];i!=-1;i=next[i]) 47 { 48 if(to[i]==fa) 49 { 50 continue; 51 } 52 dep[to[i]]=dep[x]+1; 53 f[to[i]]=x; 54 bfs(to[i],x); 55 size[x]+=size[to[i]]; 56 if(size[to[i]]>size[hson[x]]) 57 { 58 hson[x]=to[i]; 59 } 60 } 61 } 62 int up[80005],first[80005],tim; 63 inline void spfa(int x,int tt) 64 { 65 tim++; 66 first[x]=tim; 67 up[x]=tt; 68 if(!hson[x]) 69 { 70 return ; 71 } 72 spfa(hson[x],tt); 73 int i; 74 for(i=h[x];i!=-1;i=next[i]) 75 { 76 if(to[i]==f[x]||to[i]==hson[x]) 77 { 78 continue; 79 } 80 spfa(to[i],to[i]); 81 } 82 } 83 inline int lca(int x,int y) 84 { 85 int res=0; 86 while(up[x]!=up[y]) 87 { 88 if(dep[up[x]]<dep[up[y]]) 89 { 90 swap(x,y); 91 } 92 res+=query(first[x])-query(first[up[x]]-1); 93 x=f[up[x]]; 94 } 95 if(dep[x]>dep[y]) 96 { 97 swap(x,y); 98 } 99 res+=query(first[y])-query(first[x]-1); 100 return res; 101 } 102 struct stu 103 { 104 int op,l,r,id,x; 105 }; 106 stu a[240005]; 107 int ans[80005]; 108 int m[240005]; 109 stu q1[240005],q2[240005]; 110 inline void erfen(int l,int r,int sl,int sr) 111 { 112 if(sl>sr) 113 { 114 return ; 115 } 116 if(l==r) 117 { 118 int i; 119 for(i=sl;i<=sr;i++) 120 { 121 if(a[i].op!=2) 122 { 123 continue; 124 } 125 ans[a[i].id]=l; 126 } 127 return ; 128 } 129 int i,mid=(l+r)>>1,k,cnt1=0,cnt2=0; 130 for(i=sl;i<=sr;i++) 131 { 132 if(a[i].op==0) 133 { 134 if(a[i].x<=mid) 135 { 136 add(first[a[i].l],1); 137 m[i]=0; 138 } 139 else 140 { 141 m[i]=1; 142 } 143 continue; 144 } 145 if(a[i].op==1) 146 { 147 if(a[i].x<=mid) 148 { 149 add(first[a[i].l],-1); 150 m[i]=0; 151 } 152 else 153 { 154 m[i]=1; 155 } 156 continue; 157 } 158 if(a[i].op==2) 159 { 160 k=lca(a[i].l,a[i].r); 161 if(k<a[i].x) 162 { 163 a[i].x-=k; 164 m[i]=1; 165 } 166 else 167 { 168 m[i]=0; 169 } 170 } 171 } 172 for(i=sl;i<=sr;i++) 173 { 174 if(a[i].op==0) 175 { 176 if(a[i].x<=mid) 177 { 178 add(first[a[i].l],-1); 179 } 180 } 181 if(a[i].op==1) 182 { 183 if(a[i].x<=mid) 184 { 185 add(first[a[i].l],1); 186 } 187 } 188 if(m[i]==0) 189 { 190 cnt1++; 191 q1[cnt1]=a[i]; 192 } 193 else 194 { 195 cnt2++; 196 q2[cnt2]=a[i]; 197 } 198 } 199 for(i=1;i<=cnt1;i++) 200 { 201 a[sl+i-1]=q1[i]; 202 } 203 for(i=1;i<=cnt2;i++) 204 { 205 a[sl+cnt1+i-1]=q2[i]; 206 } 207 erfen(l,mid,sl,sl+cnt1-1); 208 erfen(mid+1,r,sl+cnt1,sr); 209 } 210 int p[80005]; 211 int main() 212 { 213 memset(h,-1,sizeof(h)); 214 memset(ans,0x3f,sizeof(ans)); 215 n=read(),q=read(); 216 int i,x,y,tail=0,k,o; 217 for(i=1;i<=n;i++) 218 { 219 x=read(); 220 tail++; 221 a[tail].op=0,a[tail].l=i,a[tail].x=x; 222 p[i]=x; 223 } 224 for(i=1;i<n;i++) 225 { 226 x=read(),y=read(); 227 addedge(x,y); 228 addedge(y,x); 229 } 230 dep[1]=1; 231 bfs(1,-1); 232 spfa(1,1); 233 for(i=1;i<=n;i++) 234 { 235 add(first[i],1); 236 } 237 for(i=1;i<=q;i++) 238 { 239 k=read(),x=read(),y=read(); 240 if(k==0) 241 { 242 tail++; 243 a[tail].op=1;a[tail].l=x,a[tail].x=p[x]; 244 tail++; 245 a[tail].op=0;a[tail].l=x;a[tail].x=y; 246 p[x]=y; 247 } 248 else 249 { 250 o=lca(x,y); 251 if(o<k) 252 { 253 ans[i]=-1; 254 continue; 255 } 256 k=o-k+1; 257 tail++; 258 a[tail].op=2,a[tail].l=x,a[tail].r=y,a[tail].x=k; 259 a[tail].id=i; 260 } 261 } 262 memset(data,0,sizeof(data)); 263 erfen(0,100000000,1,tail); 264 for(i=1;i<=q;i++) 265 { 266 if(ans[i]==0x3f3f3f3f) 267 { 268 continue; 269 } 270 if(ans[i]==-1) 271 { 272 puts("invalid request!"); 273 } 274 else 275 { 276 printf("%d\n",ans[i]); 277 } 278 } 279 return 0; 280 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 剑指offer65:矩阵中的路径(二维数组,二分查找) 2019-09-02
- 二分法(一):二分法的基本思想 2019-08-16
- 二分法(四):采用二分法解决“最大化平均值”问题 2019-08-16
- 二分法(二):采用二分法解决“最小化最大值问题” 2019-08-16
- 洛谷 P3386 【模板】二分图匹配 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash