bzoj2006 [ NOI2010 ] && bzoj3784 --點分治+線段樹+堆。本站提示廣大學習愛好者：（bzoj2006 [ NOI2010 ] && bzoj3784 --點分治+線段樹+堆）文章只能為提供參考，不一定能成為您想要的結果。以下是bzoj2006 [ NOI2010 ] && bzoj3784 --點分治+線段樹+堆正文
bzoj2006:
定義一個四元組{x,l,r,w}，表示左端點在x，右端點在[l,r]的超級和弦的最大美妙度在將w作為右端點時取到，w可以用前綴和+線段樹/ST表求出。
對於每個i，我們將{i,i+L-1,i+R-1,w}放入一個大根堆中，每次取出美妙度最大的一個加到答案中，並將{i,l,w-1,x},{i,w+1,r,x}放入堆中。
這樣就相當於將左端點在i、右端點在w的超級和弦去掉。做k次就可以了。
代碼：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<algorithm>
6 using namespace std;
7 inline char Nc(){
8 static char buf[100000],*p1=buf,*p2=buf;
9 if(p1==p2){
10 p2=(p1=buf)+fread(buf,1,100000,stdin);
11 if(p1==p2)return EOF;
12 }
13 return *p1++;
14 }
15 inline void Read(int& x){
16 char c=Nc(),b=1;
17 for(;c<'0'||c>'9';c=Nc())if(c=='-')b=-1;
18 for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());x*=b;
19 }
20 inline int _Max(int x,int y){return x<y?y:x;}
21 inline int _Min(int x,int y){return x<y?x:y;}
22 #define N 500010
23 #define INF 2147483647
24 int i,j,k,n,m,c[N<<2],s[N],x,L,R,t[N<<2];
25 struct G{
26 int x,l,r,w;
27 G(){}
28 G(int x,int l,int r,int w):x(x),l(l),r(r),w(w){}
29 bool operator<(G a)const{
30 return s[w]-s[x-1]<s[a.w]-s[a.x-1];
31 }
32 }tmp;
33 priority_queue<G>q;
34 long long Ans;
35 inline int Query(int Node,int l,int r,int L,int R){
36 if(l>R||r<L)return 0;
37 if(l>=L&&r<=R)return Node;
38 int Mid=l+r>>1;
39 int Q1=Query(Node<<1,l,Mid,L,R),Q2=Query(Node<<1|1,Mid+1,r,L,R);
40 return c[Q1]>c[Q2]?Q1:Q2;
41 }
42 inline void Build(int Node,int l,int r){
43 if(l==r){
44 c[Node]=s[l];
45 t[Node]=l;
46 return;
47 }
48 int Mid=l+r>>1;
49 Build(Node<<1,l,Mid);
50 Build(Node<<1|1,Mid+1,r);
51 if(c[Node<<1]>c[Node<<1|1])c[Node]=c[Node<<1],t[Node]=t[Node<<1];else
52 c[Node]=c[Node<<1|1],t[Node]=t[Node<<1|1];
53 }
54 int main()
55 {
56 Read(n);Read(k);Read(L);Read(R);
57 for(i=1;i<=n;i++)Read(x),s[i]=s[i-1]+x;
58 Build(1,1,n);c[0]=-INF;
59 for(i=1;i+L-1<=n;i++)q.push(G(i,i+L-1,_Min(i+R-1,n),t[Query(1,1,n,i+L-1,_Min(i+R-1,n))]));
60 while(k--){
61 tmp=q.top();q.pop();
62 Ans+=s[tmp.w]-s[tmp.x-1];
63 if(tmp.w>tmp.l)q.push(G(tmp.x,tmp.l,tmp.w-1,t[Query(1,1,n,tmp.l,tmp.w-1)]));
64 if(tmp.w<tmp.r)q.push(G(tmp.x,tmp.w+1,tmp.r,t[Query(1,1,n,tmp.w+1,tmp.r)]));
65 }
66 printf("%lld",Ans);
67 return 0;
68 }
bzoj2006
bzoj3784:
這題是bzoj2006的樹上版本。考慮點分治。分治到一個點時，將所有點到它的距離d求出，那麼一個子樹中的點的d加上另一個子樹中的點的d就是一條路徑。
將dfs到的點依次加入一個序列，那麼序列中每個點能到的所有點就是一個區間[l,r]，就可以轉化為bzoj2006了。
具體看代碼。
代碼：
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<queue>
5 using namespace std;
6 inline char Nc(){
7 static char buf[100000],*p1=buf,*p2=buf;
8 if(p1==p2){
9 p2=(p1=buf)+fread(buf,1,100000,stdin);
10 if(p1==p2)return EOF;
11 }
12 return *p1++;
13 }
14 inline void Read(int& x){
15 char c=Nc(),b=1;
16 for(;c<'0'||c>'9';c=Nc())if(c=='-')b=-1;
17 for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());x*=b;
18 }
19 inline int _Max(int x,int y){return x>y?x:y;}
20 #define N 50010
21 #define INF 2147483647
22 struct Edge{
23 int t,nx,w;
24 }e[N<<1];
25 int i,j,k,n,Cnt,m,l[N<<5],r[N<<5],x,y,z,L,R,c[N<<6],Num,p[N<<6],a[N<<5],h[N],f[N],d[N],Size[N],Rt,Sum;
26 bool b[N];
27 struct G{
28 int l,r,w,t;
29 G(){}
30 G(int l,int r,int w,int t):l(l),r(r),w(w),t(t){}
31 bool operator<(G b)const{
32 return a[t]+w<a[b.t]+b.w;
33 }
34 }tmp;
35 priority_queue<G>q;
36 inline void Add(int x,int y,int z){e[++Num].t=y;e[Num].w=z;e[Num].nx=h[x];h[x]=Num;}
37 inline void Get_root(int x,int F){
38 f[x]=0;Size[x]=1;
39 for(int i=h[x];i;i=e[i].nx){
40 int v=e[i].t;
41 if(!b[v]&&v!=F){
42 Get_root(v,x);
43 Size[x]+=Size[v];
44 f[x]=_Max(f[x],Size[v]);
45 }
46 }
47 f[x]=_Max(f[x],Sum-Size[x]);
48 if(f[x]<f[Rt])Rt=x;
49 }
50 inline void Dfs(int x,int F){
51 a[++Cnt]=d[x];l[Cnt]=L;r[Cnt]=R;
52 for(int i=h[x];i;i=e[i].nx){
53 int v=e[i].t;
54 if(!b[v]&&v!=F)d[v]=d[x]+e[i].w,Dfs(v,x);
55 }
56 }
57 inline void Solve(int x){
58 a[++Cnt]=0;d[x]=0;L=R=Cnt;b[x]=1;
59 for(int i=h[x];i;i=e[i].nx){
60 int v=e[i].t;
61 if(!b[v])d[v]=e[i].w,Dfs(v,x),R=Cnt;
62 }
63 for(int i=h[x];i;i=e[i].nx){
64 int v=e[i].t;
65 if(!b[v]){
66 f[Rt=0]=Size[v]+1;Sum=Size[v];
67 Get_root(v,x);
68 Solve(Rt);
69 }
70 }
71 }
72 inline void Build(int Node,int l,int r){
73 if(l==r){
74 c[Node]=a[l];
75 p[Node]=l;
76 return;
77 }
78 int Mid=l+r>>1;
79 Build(Node<<1,l,Mid);
80 Build(Node<<1|1,Mid+1,r);
81 if(c[Node<<1]>c[Node<<1|1])c[Node]=c[Node<<1],p[Node]=p[Node<<1];else
82 c[Node]=c[Node<<1|1],p[Node]=p[Node<<1|1];
83 }
84 inline int Query(int Node,int l,int r,int L,int R){
85 if(l>R||r<L)return 0;
86 if(l>=L&&r<=R)return Node;
87 int Mid=l+r>>1;
88 int Q1=Query(Node<<1,l,Mid,L,R),Q2=Query(Node<<1|1,Mid+1,r,L,R);
89 return c[Q1]>c[Q2]?Q1:Q2;
90 }
91 int main()
92 {
93 Read(n);Read(m);
94 for(i=1;i<n;i++)Read(x),Read(y),Read(z),Add(x,y,z),Add(y,x,z);
95 f[Rt=0]=n+1;Sum=n;Get_root(1,0);
96 Solve(Rt);
97 Build(1,1,Cnt);c[0]=-INF;
98 for(i=1;i<=Cnt;i++)if(l[i])q.push(G(l[i],r[i],a[i],p[Query(1,1,Cnt,l[i],r[i])]));
99 while(m--){
100 tmp=q.top();q.pop();
101 printf("%d\n",tmp.w+a[tmp.t]);
102 if(tmp.t>tmp.l)q.push(G(tmp.l,tmp.t-1,tmp.w,p[Query(1,1,Cnt,tmp.l,tmp.t-1)]));
103 if(tmp.t<tmp.r)q.push(G(tmp.t+1,tmp.r,tmp.w,p[Query(1,1,Cnt,tmp.t+1,tmp.r)]));
104 }
105 return 0;
106 }
bzoj3784
