[关闭]
@ivorysi 2018-01-02T08:48:01.000000Z 字数 30116 阅读 807

分治学习笔记

笔记

平面分治

HDU 1007 Quoit Design

Problem Description

Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.
Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

Input

The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

Output

For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input

2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

Sample Output

0.71
0.00
0.75

题解

这是一道平面分治
我们把平面分成两部分，每部分点数相等，然后我们考虑跨过中间那条线的距离
我们对于y坐标排序，边分治边归并排序，要保证这个坐标是是x-d,x+d，d是左右两边的点距离的最小值
然后每个点对于它对面的点进行匹配，要保证对面的点的y坐标要小于这个点的y，然后判断一下这两个y距离是不是大于d，如果大于就可以跳出
匹配的次数不会超过3次，因为对面的点和这面的某个点p距离小于d的不超过3个，否则d可以更小

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. //#define ivorysi
  12. using namespace std;
  13. struct Point {
  14.     double x,y;
  15.     Point() {}
  16.     Point(double _x,double _y) {
  17.     x=_x;y=_y;
  18.     }
  19.     bool operator < (const Point &rhs) const{
  20.     return x<rhs.x;
  21.     }
  22.     friend Point operator -(const Point &a,const Point &b) {
  23.     return Point(a.x-b.x,a.y-b.y);
  24.     }
  25.     double norm() {
  26.     return sqrt(x*x+y*y);
  27.     }
  28. }p[100005];
  29. Point a[100005],b[100005],c[100005];
  30. int b_cnt=0,c_cnt=0;
  31. double solve(int l,int r) {
  32.     if(l==r) return 1e18;
  33.     int mid=(l+r)>>1;
  34.     double x0=(p[mid].x+p[mid+1].x)/2.0;
  35.     double d=min(solve(l,mid),solve(mid+1,r));
  36.     b_cnt=0;
  37.     c_cnt=0;
  38.     int L=l,R=mid+1,tot=l;
  39.     while(L<=mid && R<=r) {
  40.     if(p[L].y<p[R].y) {
  41.         if(p[L].x>=(x0-d)) b[++b_cnt]=p[L];
  42.         a[tot++]=p[L++];
  43.     }
  44.     else {
  45.         if(p[R].x<=(x0+d)) c[++c_cnt]=p[R];
  46.         a[tot++]=p[R++];
  47.     }
  48.     }
  49.     while(L<=mid) {
  50.     if(p[L].x>(x0-d)) b[++b_cnt]=p[L];
  51.     a[tot++]=p[L++];
  52.     }
  53.     while(R<=r) {
  54.     if(p[R].x<(x0+d)) c[++c_cnt]=p[R];
  55.     a[tot++]=p[R++];
  56.     }
  57.     siji(i,l,r) p[i]=a[i];
  58.     int z=1,s=1;
  59.     while(z<=b_cnt || s<=c_cnt) {
  60.     if(z<=b_cnt && (s>c_cnt || b[z].y<c[s].y) ) {
  61.         gongzi(i,s-1,1) {
  62.         if(b[z].y-d>=c[i].y) break;
  63.         d=min(d,(c[i]-b[z]).norm());
  64.         }
  65.         ++z;
  66.     }
  67.     else {
  68.         gongzi(i,z-1,1) {
  69.         if(c[s].y-d>=b[i].y) break;
  70.         d=min(d,(c[s]-b[i]).norm());
  71.         }
  72.         ++s;
  73.     }
  74.     }
  75.     return d;
  76. }
  77. int main() {
  78. #ifdef ivorysi
  79.     freopen("f1.in","r",stdin);
  80. #endif
  81.     int n;
  82.     while(scanf("%d",&n)!=EOF) {
  83.     if(n==0) break;
  84.     siji(i,1,n) {
  85.         scanf("%lf%lf",&p[i].x,&p[i].y);
  86.     }
  87.     sort(p+1,p+n+1);
  88.     printf("%.2lf\n",solve(1,n)/2.0);
  89.     }
  91. }

HDU 5696 区间的价值

Problem Description

我们定义“区间的价值”为一段区间的最大值*最小值。
一个区间左端点在L，右端点在R，那么该区间的长度为(R−L+1)。
现在聪明的杰西想要知道，对于长度为k的区间，最大价值的区间价值是多少。
当然，由于这个问题过于简单。
我们肯定得加强一下。
我们想要知道的是，对于长度为1∼n的区间，最大价值的区间价值分别是多少。

样例解释：

长度为1的最优区间为2−2 答案为6∗6
长度为2的最优区间为4−5 答案为4∗4
长度为3的最优区间为2−4 答案为2∗6
长度为4的最优区间为2−5 答案为2∗6
长度为5的最优区间为1−5 答案为1∗6

Input

多组测试数据
第一行一个数n(1≤n≤100000)。
第二行n个正整数(1≤ai≤109)，下标从1开始。
由于某种不可抗力，ai的值将会是1∼109内随机产生的一个数。（除了样例）

Output

输出共n行，第i行表示区间长度为i的区间中最大的区间价值。

Sample Input

5
1 6 2 4 4

Sample Output

36
16
12
12
6

题解

这道题我们就分治，每次找到最小值，然后分成左右两个部分
找到当前每个长度的最大值，然后从短的往长的更新（因为我们强制要求了最小值就是我们找到的最小值）
然后更新一遍ans
因为数据随机所以不会被卡

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MAXN 100005
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll ans[MAXN],a[MAXN],tmp[MAXN];
  16. void solve(int l,int r) {
  17.     if(r<l) {
  18.     return;
  19.     }
  20.     int p=l;
  21.     siji(i,l+1,r) {
  22.     if(a[i]<a[p]) p=i;
  23.     }
  24.     siji(i,1,r-l+1) tmp[i]=0;
  25.     gongzi(i,p,l) {
  26.     tmp[p-i+1]=max(tmp[p-i+1],a[i]*a[p]);
  27.     }
  28.     siji(i,p,r) {
  29.     tmp[i-p+1]=max(tmp[i-p+1],a[i]*a[p]);
  30.     }
  31.     siji(i,1,r-l+1) {
  32.     tmp[i]=max(tmp[i],tmp[i-1]);
  33.     ans[i]=max(ans[i],tmp[i]);
  34.     }
  35.     solve(l,p-1);
  36.     solve(p+1,r);
  37. }
  38. int main() {
  39. #ifdef ivorysi
  40.     freopen("f1.in","r",stdin);
  41. #endif
  42.     int n;
  43.     while(scanf("%d",&n)!=EOF) {
  44.     siji(i,1,n) {
  45.         scanf("%lld",&a[i]);
  46.     }
  47.     memset(ans,0,sizeof(ans));
  48.     solve(1,n);
  50.     siji(i,1,n) {
  51.         printf("%lld\n",ans[i]);
  52.     }
  53.     }
  54. }

codeforces 97B. Superset

A set of points on a plane is called good, if for any two points at least one of the three conditions is true:

those two points lie on same horizontal line;
those two points lie on same vertical line;
the rectangle, with corners in these two points, contains inside or on its borders at least one point of the set, other than these two. We mean here a rectangle with sides parallel to coordinates' axes, the so-called bounding box of the two points.

You are given a set consisting of n points on a plane. Find any good superset of the given set whose size would not exceed 2·105 points.

Input

The first line contains an integer n (1 ≤ n ≤ 104) — the number of points in the initial set. Next n lines describe the set's points. Each line contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — a corresponding point's coordinates. It is guaranteed that all the points are different.

Output

Print on the first line the number of points m (n ≤ m ≤ 2·105) in a good superset, print on next m lines the points. The absolute value of the points' coordinates should not exceed 109. Note that you should not minimize m, it is enough to find any good superset of the given set, whose size does not exceed 2·105.
All points in the superset should have integer coordinates.

Examples

Input

2
1 1
2 2

Output

3
1 1
2 2
1 2

题解

这道题的题面意思是找到一个更大的集合包含给出的集合，这个集合随便找但是大小不要超过2×10^5
使得任意两点之间满足下列三种条件之一
1.两点在同一条水平线
2.两点在同一条竖直线
3.两点构成的矩形中间包含一个点，可以在边界和里面（矩形的边和x轴y轴平行）

我们可以将点排序然后分成两份，让左右边每一个点向中间点所在的竖直线做一条垂线，这样做出的点肯定和剩下所有点都合法，然后递归的层数不会超过log n层，那么我们总共做出的点的个数不会超过n log n个

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. int n;
  15. struct Point {
  16.     int x,y;
  17.     Point() {}
  18.     Point(int _x,int _y) {
  19.     x=_x;y=_y;
  20.     }
  21.     bool operator < (const Point &rhs) const {
  22.     return x<rhs.x || (x==rhs.x && y<rhs.y);
  23.     }
  24.     bool operator == (const Point &rhs) const {
  25.     return x==rhs.x && y==rhs.y;
  26.     }
  27. }p[10005];
  28. set<Point> s;
  29. void solve(int l,int r) {
  30.     if(r<=l) return;
  31.     int mid=(l+r)>>1;
  32.     siji(i,l,r) {
  33.     s.insert(Point(p[mid].x,p[i].y));
  34.     }
  35.     solve(l,mid-1);
  36.     solve(mid+1,r);
  37. }
  38. int main() {
  39. #ifdef ivorysi
  40.     freopen("f1.in","r",stdin);
  41. #endif
  42.     scanf("%d",&n);
  43.     siji(i,1,n) {
  44.     scanf("%d%d",&p[i].x,&p[i].y);
  45.     s.insert(p[i]);
  46.     }
  47.     sort(p+1,p+n+1);
  48.     solve(1,n);
  49.     set<Point>::iterator iter;
  50.     printf("%d\n",s.size());
  51.     for(iter=s.begin();iter!=s.end();++iter) {
  52.     printf("%d %d\n",iter->x,iter->y);
  53.     }
  54.     return 0;
  55. }

2458: [BeiJing2011]最小三角形

Description

Xaviera现在遇到了一个有趣的问题。
平面上有N个点，Xaviera想找出周长最小的三角形。
由于点非常多，分布也非常乱，所以Xaviera想请你来解决这个问题。
为了减小问题的难度，这里的三角形也包括共线的三点。

Input

第一行包含一个整数N表示点的个数。
接下来N行每行有两个整数，表示这个点的坐标。

Output

输出只有一行，包含一个6位小数，为周长最短的三角形的周长（四舍五入）。

Sample Input

4
1 1
2 3
3 3
3 4

Sample Output

3.414214

HINT

100%的数据中N≤200000。

题解

这是一道平面分治的题，我一开始认为只有两个相邻的点能做底边……
然后又开始枚举左边一个点，右边一个点，第三个点从右边点开始往上找，找到和右边的点距离大于d/2的就跳出
又gg了
因为有些时候，可能y坐标靠上的，和某个点距离反而小………………
然后我改对了我枚举的姿势
然后我的冒泡排序（对于三个点排序）写跪了，把i+1写成l+1了

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <cmath>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define esp 1e-8
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int n;
  17. struct Point {
  18.     double x,y;
  19.     Point() {}
  20.     Point(double _x,double _y) {
  21.     x=_x;y=_y;
  22.     }
  23.     bool operator < (const Point &rhs) const {
  24.     return x<rhs.x || (x==rhs.x && y<rhs.y);
  25.     }
  26.     bool operator == (const Point &rhs) const {
  27.     return x==rhs.x && y==rhs.y;
  28.     }
  29.     friend Point operator - (const Point &a,const Point &b) {
  30.     return Point(a.x-b.x,a.y-b.y);
  31.     } 
  32.     double norm() {
  33.     return sqrt(x*x+y*y);
  34.     }
  35. }p[400005];
  36. Point a[400005],b[400005],c[400005];
  37. int b_cnt,c_cnt;
  38. double calc(Point l,Point z,Point s) {
  39.     return (l-z).norm()+(l-s).norm()+(z-s).norm();
  40. }
  41. double solve(int l,int r) {
  42.     if(r==l) {
  43.     return 1e20;
  44.     }
  45.     int mid=(l+r)>>1;
  46.     double x0=(p[mid].x+p[mid+1].x)/2.0;
  47.     double d=min(solve(l,mid),solve(mid+1,r));
  48.     b_cnt=c_cnt=0;
  49.     int L=l,R=mid+1,tot=l;
  50.     while(L<=mid && R<=r) {
  51.     if(p[L].y<p[R].y) {
  52.         if(p[L].x>=x0-d/2) b[++b_cnt]=p[L];
  53.         a[tot++]=p[L++];
  54.     }
  55.     else {
  56.         if(p[R].x<=x0+d/2) c[++c_cnt]=p[R];
  57.         a[tot++]=p[R++];
  58.     }
  59.     }
  60.     while(L<=mid) {
  61.     if(p[L].x>=x0-d/2) b[++b_cnt]=p[L];
  62.     a[tot++]=p[L++];
  63.     }
  64.     while(R<=r) {
  65.     if(p[R].x<=x0+d/2) c[++c_cnt]=p[R];
  66.     a[tot++]=p[R++];
  67.     }
  68.     siji(i,l,r) p[i]=a[i];
  69.     if(l+1==r) return 1e20;
  70.     int pos=1;
  71.     siji(i,1,b_cnt) {
  72.     while(pos<=c_cnt && b[i].y-c[pos].y >d/2) ++pos;
  73.     siji(j,pos,c_cnt) {
  74.         if(fabs(c[j].y-b[i].y) > d/2) break; 
  75.         siji(k,j+1,c_cnt) {
  76.         if(fabs(c[k].y-b[i].y)>d/2) break;
  77.         d=min(d,calc(b[i],c[k],c[j]));
  78.         }
  79.     }
  80.     }
  81.     pos=1;
  82.     siji(i,1,c_cnt) {
  83.     while(pos<=b_cnt && c[i].y-b[pos].y >d/2) ++pos;
  84.     siji(j,pos,b_cnt) {
  85.         if(fabs(b[j].y-c[i].y) > d/2) break;
  86.         siji(k,j+1,b_cnt) {
  87.         if(fabs(b[k].y-c[i].y)>d/2) break;
  88.         d=min(d,calc(c[i],b[j],b[k]));
  89.         }
  90.     }
  91.     }
  92.     return d;
  93. }
  94. int main() {
  95. #ifdef ivorysi
  96.     freopen("f1.in","r",stdin);
  97. #endif
  98.     scanf("%d",&n);
  99.     siji(i,1,n) {
  100.     scanf("%lf%lf",&p[i].x,&p[i].y);
  101.     }
  102.     sort(p+1,p+n+1);
  103.     printf("%.6lf\n",solve(1,n));
  104.     return 0;
  105. }

POJ 1741 Tree

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0

Sample Output

8

题解

这道题是树分治的板子题
我们把树按照重心划分，路径有三种情况，一是过重心，一是不过重心，一是以重心为端点
不过重心可以靠递归继续完成
而过重心和以重心为端点的，直接计算，d_u+d_v<=k，然后去掉所有u和v在一棵子树里的

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <cmath>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define esp 1e-8
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int n,k;
  17. struct node {
  18.     int val,to,next;
  19. }edge[200005];
  20. int head[20005],sumedge,fa[20005],size[20005],son[20005],dis[20005],d[20005];
  21. ll ans;
  22. bool vis[20005];
  23. void add(int u,int v,int w) {
  24.     edge[++sumedge].to=v;
  25.     edge[sumedge].val=w;
  26.     edge[sumedge].next=head[u];
  27.     head[u]=sumedge;
  28. }
  29. void addtwo(int u,int v,int w) {
  30.     add(u,v,w);
  31.     add(v,u,w);
  32. }
  33. int que[20005],ql,qr;
  34. int calcG(int st) {
  35.     fa[st]=0;qr=1;
  36.     que[ql=1]=st;
  37.     while(ql<=qr) {
  38.     int u=que[ql++];
  39.     size[u]=1;son[u]=0;
  40.     for(int i=head[u];i;i=edge[i].next) {
  41.         int v=edge[i].to;
  42.         if(!vis[v] && v!=fa[u]) {
  43.         que[++qr]=v;
  44.         fa[v]=u;
  45.         }
  46.     }
  47.     }
  48.     int res=0,mx=qr;
  49.     gongzi(i,qr,1) {
  50.     int u=que[i];
  51.     son[u]=max(son[u],qr-size[u]);
  52.     if(son[u]<mx) {
  53.         mx=son[u];
  54.         res=u;
  55.     }
  56.     size[fa[u]]+=size[u];
  57.     if(size[u] > son[fa[u]]) son[fa[u]]=size[u];
  58.     }
  59.     return res;
  60. }
  61. ll calc(int st,int di) {
  62.     dis[st]=di;
  63.     fa[st]=0;que[ql=1]=st;qr=1;
  64.     d[1]=di;
  65.     while(ql<=qr) {
  66.     int u=que[ql++];
  67.     for(int i=head[u];i;i=edge[i].next) {
  68.         int v=edge[i].to;
  69.         if(!vis[v] && v!=fa[u]) {
  70.         que[++qr]=v;
  71.         dis[v]=dis[u]+edge[i].val;
  72.         d[qr]=dis[v];
  73.         fa[v]=u;
  74.         }
  75.     }
  76.     }
  77.     int l=1,r=qr;
  78.     sort(d+1,d+qr+1);
  79.     ll res=0;
  80.     while(l<r) {
  81.     if(d[l]+d[r]<=k) {res+=r-l; ++l;}
  82.     else --r;
  83.     }
  84.     return res;
  85. }
  86. void solve(int u) {
  87.     int G=calcG(u);
  88.     vis[G]=1;
  89.     ans+=calc(G,0);
  90.     for(int i=head[G];i;i=edge[i].next) {
  91.     int v=edge[i].to;
  92.     if(!vis[v]) ans-=calc(v,edge[i].val);
  93.     }
  94.     for(int i=head[G];i;i=edge[i].next) {
  95.     int v=edge[i].to;
  96.     if(!vis[v]) solve(v);
  97.     }
  98. }
  99. int main() {
  100. #ifdef ivorysi
  101.     freopen("f1.in","r",stdin);
  102. #endif
  103.     while(scanf("%d%d",&n,&k)!=EOF) {
  104.     if(n+k==0) break;
  105.     ans=0;
  106.     sumedge=0;
  107.     memset(head,0,sizeof(head));
  108.     memset(vis,0,sizeof(vis));
  109.     memset(dis,0,sizeof(dis));
  110.     int u,v,w;
  111.     xiaosiji(i,1,n) {
  112.         scanf("%d%d%d",&u,&v,&w);
  113.         addtwo(u,v,w);
  114.     }
  115.     solve(1);
  116.     printf("%lld\n",ans);
  117.     }
  118.     return 0;
  119. }

BZOJ 2152: 聪聪可可

Description

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。

Output

以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。

Sample Input

5
1 2 1
1 3 2
1 4 1
2 5 3

Sample Output

13/25

【样例说明】

13组点对分别是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。

题解

树分治的又一道板题
边的三种情况，然后去除掉两个点在同一子树的，之后递归处理

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <cmath>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define esp 1e-8
  13. #define MAXN 20005
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,k;
  18. struct node {
  19.     int to,next;
  20.     ll val;
  21. }edge[MAXN*2];
  22. int head[MAXN],sumedge,fa[MAXN],size[MAXN],son[MAXN];
  23. ll ans,dis[MAXN],cnt[10];
  24. bool vis[20005];
  25. void add(int u,int v,ll w) {
  26.     edge[++sumedge].to=v;
  27.     edge[sumedge].val=w;
  28.     edge[sumedge].next=head[u];
  29.     head[u]=sumedge;
  30. }
  31. void addtwo(int u,int v,ll w) {
  32.     add(u,v,w);
  33.     add(v,u,w);
  34. }
  35. int que[20005],ql,qr;
  36. int calcG(int st) {
  37.     fa[st]=0;qr=1;
  38.     que[ql=1]=st;
  39.     while(ql<=qr) {
  40.     int u=que[ql++];
  41.     size[u]=1;son[u]=0;
  42.     for(int i=head[u];i;i=edge[i].next) {
  43.         int v=edge[i].to;
  44.         if(!vis[v] && v!=fa[u]) {
  45.         que[++qr]=v;
  46.         fa[v]=u;
  47.         }
  48.     }
  49.     }
  50.     int res=0,mx=qr;
  51.     gongzi(i,qr,1) {
  52.     int u=que[i];
  53.     son[u]=max(son[u],qr-size[u]);
  54.     if(son[u]<mx) {
  55.         mx=son[u];
  56.         res=u;
  57.     }
  58.     size[fa[u]]+=size[u];
  59.     if(size[u] > son[fa[u]]) son[fa[u]]=size[u];
  60.     }
  61.     return res;
  62. }
  63. ll calc(int st,int di) {
  64.     dis[st]=di;
  65.     fa[st]=0;que[ql=1]=st;qr=1;
  66.     memset(cnt,0,sizeof(cnt));
  67.     cnt[dis[st]%3]++;
  68.     while(ql<=qr) {
  69.     int u=que[ql++];
  70.     for(int i=head[u];i;i=edge[i].next) {
  71.         int v=edge[i].to;
  72.         if(!vis[v] && v!=fa[u]) {
  73.         que[++qr]=v;
  74.         dis[v]=dis[u]+edge[i].val;
  75.         cnt[dis[v]%3]++;
  76.         fa[v]=u;
  77.         }
  78.     }
  79.     }
  80.     ll res=0;
  81.     siji(i,1,qr) {
  82.     res+=cnt[(3-(dis[que[i]]%3)) %3];
  83.     }
  84.     return res;
  85. }
  86. void solve(int u) {
  87.     int G=calcG(u);
  88.     vis[G]=1;
  89.     ans+=calc(G,0);
  90.     for(int i=head[G];i;i=edge[i].next) {
  91.     int v=edge[i].to;
  92.     if(!vis[v]) ans-=calc(v,edge[i].val);
  93.     }
  94.     for(int i=head[G];i;i=edge[i].next) {
  95.     int v=edge[i].to;
  96.     if(!vis[v]) solve(v);
  97.     }
  98. }
  99. ll gcd(ll a,ll b) {
  100.     return b==0 ? a : gcd(b,a%b);
  101. }
  103. int main() {
  104. #ifdef ivorysi
  105.     freopen("f1.in","r",stdin);
  106. #endif
  107.     while(scanf("%d",&n)!=EOF) {
  108.     if(n+k==0) break;
  109.     ans=0;
  110.     sumedge=0;
  111.     memset(head,0,sizeof(head));
  112.     memset(vis,0,sizeof(vis));
  113.     memset(dis,0,sizeof(dis));
  114.     int u,v,w;
  115.     xiaosiji(i,1,n) {
  116.         scanf("%d%d%d",&u,&v,&w);
  117.         addtwo(u,v,w);
  118.     }
  119.     solve(1);
  120.     ll down=(ll)n*n;
  121.     ll g=gcd(down,ans);
  122.     ans/=g;down/=g;
  123.     printf("%lld/%lld\n",ans,down);
  124.     }
  125.     return 0;
  126. }

BZOJ 1758: [Wc2010]重建计划

题面大意

给出一棵树，求一条路径上边的边数在[L,U]之间，要求每条路径的平均值最大，求这个最大的平均值

数据范围

N<=1000000

题解

树分治的题总是很轻易的就非常恶心
这道题一看就是分数规划……然后怎么判断有没有解就mengbier
后来说是把每条边的边权都减去二分到的数值，然后求一条路径边数在[L,U]之间，权值大于0
这个树分治的思路很明显，合并两棵子树的时候可以用单调队列（然而我单调队列总是跪）
然而……这道题有人加了一个新的数据，必须要求我们对于每个重心的子树按深度从小到大合并
这样时间复杂度才是严格的

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 100005
  13. #define esp 1e-8
  14. #define pii pair<int,int>
  15. #define fi first
  16. #define se second
  17. //#define ivorysi
  18. using namespace std;
  19. typedef long long ll;
  20. int n,S,T;
  21. int read() {
  22.     char c=getchar();
  23.     int res=0;
  24.     while(c<'0' || c>'9') c=getchar();
  25.     while(c>='0' && c<='9') {
  26.     res=res*10+c-'0';
  27.     c=getchar();
  28.     }
  29.     return res;
  30. }
  31. struct node {
  32.     int to,next,val;
  33. }edge[MAXN*2];
  34. int sumedge,head[MAXN];
  35. void add(int u,int v,int c) {
  36.     edge[++sumedge].to=v;
  37.     edge[sumedge].next=head[u];
  38.     edge[sumedge].val=c;
  39.     head[u]=sumedge;
  40. }
  41. void addtwo(int u,int v,int c) {
  42.     add(u,v,c);
  43.     add(v,u,c);
  44. }
  45. int Gr[MAXN],tot;
  46. bool vis[MAXN];
  47. int que[MAXN],ql,qr,fa[MAXN],son[MAXN],size[MAXN],DEP[MAXN];
  48. double L[MAXN],Z[MAXN],dis[MAXN];
  49. vector<pii> ver[MAXN];
  50. int calcG(int st) {
  51.     que[ql=qr=1]=st;
  52.     fa[st]=0;
  53.     while(ql<=qr) {
  54.     int u=que[ql++];
  55.     size[u]=1;son[u]=0;
  56.     for(int i=head[u];i;i=edge[i].next) {
  57.         int v=edge[i].to;
  58.         if(!vis[v] && v!=fa[u]) {
  59.         fa[v]=u;
  60.         que[++qr]=v;
  61.         }
  62.     }
  63.     }
  64.     int res=0,mx=qr;
  65.     gongzi(i,qr,1) {
  66.     int u=que[i];
  67.     son[u]=max(son[u],qr-size[u]);
  68.     if(son[u]<mx) {
  69.         res=u;mx=son[u];
  70.     }
  71.     size[fa[u]]+=size[u];
  72.     son[fa[u]]=max(son[fa[u]],size[u]);
  73.     }
  74.     return res;
  75. }
  77. void pre_dfs(int u) {
  78.     Gr[++tot]=calcG(u);
  79.     vis[Gr[tot]]=1;
  80.     for(int i=head[Gr[tot]];i;i=edge[i].next) {
  81.     int v=edge[i].to;
  82.     if(!vis[v]) pre_dfs(v);
  83.     }
  84. }
  85. int dep[MAXN],Ln,Zn;
  86. void calc(int st,double di,double dec) {
  87.     que[ql=qr=1]=st;fa[st]=0;
  88.     dis[st]=di;dep[st]=1;
  89.     Zn=1;
  90.     while(ql<=qr) {
  91.     int u=que[ql++];
  92.     for(int i=head[u];i;i=edge[i].next) {
  93.         int v=edge[i].to;
  94.         if(!vis[v] && v!=fa[u]) {
  95.         que[++qr]=v;
  96.         fa[v]=u;
  97.         dis[v]=dis[u]+(double)edge[i].val-dec;
  98.         dep[v]=dep[u]+1;
  99.         Zn=dep[v];
  100.         }
  101.     }
  102.     }
  103.     siji(i,1,qr) {
  104.     Z[dep[que[i]]]=max(Z[dep[que[i]]],dis[que[i]]);
  105.     }
  106. }
  107. int dfs_for_dep(int u,int fa) {
  108.     int res=0;
  109.     for(int i=head[u];i;i=edge[i].next) {
  110.     int v=edge[i].to;
  111.     if(!vis[v] && v!=fa) {
  112.         res=max(res,dfs_for_dep(v,u));
  113.     }
  114.     }
  115.     return res+1;
  116. }
  117. bool check(double mid) {
  118.     memset(vis,0,sizeof(vis));
  119.     siji(i,1,n) {
  120.     int G=Gr[i];
  122.     vis[G]=1;
  123.     int mxdp=0;
  124.     for(int k=head[G];k;k=edge[k].next) {
  125.         int v=edge[k].to;
  126.         if(!vis[v]) {
  127.         int maxdep=dfs_for_dep(v,G);
  128.         mxdp=max(maxdep,mxdp);
  129.         ver[maxdep].push_back(make_pair(v,edge[k].val));
  130.         }
  131.     }
  132.     siji(j,1,mxdp) {L[j]=-1e13;Z[j]=-1e13;}
  133.     Ln=0;
  134.     siji(h,1,mxdp) {
  136.         int siz=ver[h].size();
  137.         xiaosiji(p,0,siz) {
  138.         calc(ver[h][p].fi,(double)ver[h][p].se-mid,mid);
  139.         ql=1,qr=0;
  140.         int b=Ln;
  141.         siji(k,1,Zn) {
  142.             while(b>=0 && k+b>=S) {
  143.             while(ql<=qr && L[que[qr]]<=L[b]) --qr;
  144.             que[++qr]=b;--b;
  145.             }
  146.             while(ql<=qr && que[ql]+k>T) {++ql;}
  147.             if(ql<=qr) {
  148.             if(L[que[ql]]+Z[k] >=0.0) {
  149.                 siji(j,1,Ln) L[j]=-1e13;
  150.                 siji(j,1,Zn) Z[j]=-1e13;
  151.                 siji(j,h,mxdp) ver[j].clear();
  152.                 return true;
  153.             }
  154.             }
  155.         }
  156.         if(Ln<Zn) Ln=Zn;
  157.         siji(k,1,Zn) {
  158.             if(k>=S && k<=T && Z[k]>=0.0) {
  159.             siji(j,1,Ln) L[j]=-1e13;
  160.             siji(j,1,Zn) Z[j]=-1e13;
  161.             siji(j,h,mxdp) ver[j].clear();
  163.             return true;
  164.             }
  166.             if(L[k]<Z[k]) L[k]=Z[k];
  167.         }
  168.         siji(k,1,Zn) Z[k]=-1e13;
  169.         }
  170.         ver[h].clear();
  171.     }
  173.     }
  175.     return false;
  176. }
  177. int main() {
  178. #ifdef ivorysi
  179.     freopen("f1.in","r",stdin);
  180. #endif
  181.     n=read();S=read();T=read();
  182.     int x,y,z;
  183.     xiaosiji(i,1,n) {
  184.         x=read();y=read();z=read();
  185.         addtwo(x,y,z);
  186.     }
  187.     pre_dfs(1);
  188.     double l=0,r=1000000.0;
  189.     int num=40;
  190.     while(num--) {
  191.     double mid=(l+r)/2.0;
  192.     if(check(mid)) l=mid;
  193.     else r=mid;
  194.     }
  195.     printf("%.3lf\n",l);
  196.     return 0;
  197. }

SPOJ FTOUR2 Free tour II

After the success of 2nd anniversary (take a look at problem FTOUR for more details), this 3rd year, Travel Agent SPOJ goes on with another discount tour.

The tour will be held on ICPC island, a miraculous one on the Pacific Ocean. We list N places (indexed from 1 to N) where the visitors can have a trip. Each road connecting them has an interest value, and this value can be negative (if there is nothing interesting to view there). Simply, these N places along with the roads connecting them form a tree structure. We will choose two places as the departure and destination of the tour.

Since September is the festival season of local inhabitants, some places are extremely crowded (we call them crowded places). Therefore, the organizer of the excursion hopes the tour will visit at most K crowded places (too tiring to visit many of them) and of course, the total number of interesting value should be maximum.

Briefly, you are given a map of N places, an integer K, and M id numbers of crowded place. Please help us to find the optimal tour. Note that we can visit each place only once (or our customers easily feel bored), also the departure and destination places don't need to be different.

Input

There is exactly one case. First one line, containing 3 integers N K M, with 1 <= N <= 200000, 0 <= K <= M, 0 <= M <= N.
Next M lines, each line includes an id number of a crowded place.
The last (N - 1) lines describe (N - 1) two-way roads connected N places, form a b i, with a, b is the id of 2 places, and i is its interest value (-10000 <= i <= 10000).

Output

Only one number, the maximum total interest value we can obtain.

Example

Input:

8 2 3
3
5
7
1 3 1
2 3 10
3 4 -2
4 5 -1
5 7 6
5 6 5
4 8 3

Output:

12

Explanation

We choose 2 and 6 as the departure and destination place, so the tour will be 2 -> 3 -> 4 -> 5 -> 6, total interest value = 10 + (-2) + (-1) + 5 = 12
* Added some unofficial cases

题解

这道题可以树分治
涉及到两棵树的合并可以用单调队列，我们先按每棵树路径上最多的拥堵结点个数分个类，从小到大处理已经合并的子树
注意重心可能也是一个拥堵节点

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 200005
  13. #define esp 1e-8
  14. #define pii pair<int,int>
  15. #define fi first
  16. #define se second
  17. #define inf 2000000005
  18. //#define ivorysi
  19. using namespace std;
  20. typedef long long ll;
  21. int n,k,m;
  23. int read() {
  24.     char c=getchar();
  25.     int neg=1,res=0;
  26.     while(c<'0' || c>'9') {
  27.     if(c=='-') neg=-1;
  28.     c=getchar();
  29.     }
  30.     while(c>='0' && c<='9') {
  31.     res=res*10+c-'0';
  32.     c=getchar();
  33.     }
  34.     return res*neg;
  35. }
  36. struct node {
  37.     int to,next,val;
  38. }edge[MAXN*4];
  39. int sumedge,head[MAXN],size[MAXN]
  40. ,son[MAXN],fa[MAXN],L[MAXN],Z[MAXN],Ln,Zn,dis[MAXN],num[MAXN],ans,crowd[MAXN];
  41. bool vis[MAXN];
  42. vector<pii> ver[MAXN];
  43. void add(int u,int v,int c) {
  44.     edge[++sumedge].to=v;
  45.     edge[sumedge].next=head[u];
  46.     edge[sumedge].val=c;
  47.     head[u]=sumedge;
  48. }
  49. void addtwo(int u,int v,int c) {
  50.     add(u,v,c);
  51.     add(v,u,c);
  52. }
  53. int que[MAXN],ql,qr;
  54. int calcG(int st) {
  55.     fa[st]=0;que[ql=qr=1]=st;
  56.     while(ql<=qr) {
  57.     int u=que[ql++];
  58.     size[u]=1,son[u]=0;
  59.     for(int i=head[u];i;i=edge[i].next) {
  60.         int v=edge[i].to;
  61.         if(!vis[v] && v!=fa[u]) {
  62.         fa[v]=u;
  63.         que[++qr]=v;
  64.         }
  65.     }
  66.     }
  67.     int res=0,mx=qr;
  68.     gongzi(i,qr,1) {
  69.     int u=que[i];
  70.     son[u]=max(son[u],qr-size[u]);
  71.     if(son[u]<mx) {
  72.         res=u;mx=son[u];
  73.     }
  74.     size[fa[u]]+=size[u];
  75.     son[fa[u]]=max(size[u],son[fa[u]]);
  76.     }
  77.     return res;
  78. }
  79. void calc(int st,int di) {
  80.     que[ql=qr=1]=st;fa[st]=0;dis[st]=di;
  81.     num[st]=crowd[st];
  82.     while(ql<=qr) {
  83.     int u=que[ql++];
  84.     for(int i=head[u];i;i=edge[i].next) {
  85.         int v=edge[i].to;
  86.         if(!vis[v] && v!=fa[u]) {
  87.         dis[v]=dis[u]+edge[i].val;
  88.         fa[v]=u;
  89.         num[v]=num[u]+crowd[v];
  90.         que[++qr]=v;
  91.         } 
  92.     }
  93.     }
  94.     gongzi(i,qr,1) {
  95.     int u=que[i];
  96.     Zn=max(Zn,num[u]);
  97.     Z[num[u]]=max(Z[num[u]],dis[u]);
  98.     }
  99. }
  100. int getdep(int u,int fa) {
  101.     int res=0;
  102.     for(int i=head[u];i;i=edge[i].next) {
  103.     int v=edge[i].to;
  104.     if(!vis[v] && v!=fa) {
  105.         res=max(res,getdep(v,u));
  106.     }
  107.     }
  108.     return res+crowd[u];
  109. }
  110. void solve(int u) {
  111.     int G=calcG(u);
  112.     vis[G]=1;
  113.     int mxdp=0;
  114.     for(int i=head[G];i;i=edge[i].next) {
  115.     int v=edge[i].to;
  116.     if(!vis[v]) {
  117.         int maxdep=getdep(v,G);
  118.         mxdp=max(mxdp,maxdep);
  119.         ver[maxdep].push_back(make_pair(v,edge[i].val));
  120.     }
  121.     }
  122.     siji(i,0,mxdp) L[i]=Z[i]=-inf;
  123.     L[0]=0;
  124.     Ln=0;
  125.     siji(i,0,mxdp) {
  126.     int siz=ver[i].size(); 
  127.     xiaosiji(j,0,siz) {
  128.         Zn=0;
  129.         calc(ver[i][j].fi,ver[i][j].se);
  130.         int b=min(k,Ln);
  131.         ql=1;qr=0;
  132.         while(b>=0) {
  133.             while(ql<=qr && L[que[qr]]<=L[b]) {--qr;}
  134.             que[++qr]=b;--b;
  135.         }
  136.         siji(h,0,Zn) {
  137.         if(Z[h]==-inf) continue;
  138.         while(ql<=qr && h+que[ql]+crowd[G]>k) ++ql;
  139.         if(ql<=qr && L[que[ql]]!=-inf) {
  140.             ans=max(ans,L[que[ql]]+Z[h]);
  141.         }
  142.         if(ql>qr || h>k) break;
  143.         }
  144.         if(Ln<Zn) Ln=Zn;
  145.         siji(h,0,Zn) L[h]=max(L[h],Z[h]);
  146.         siji(h,0,Zn) Z[h]=-inf;
  147.     }
  148.     ver[i].clear();
  149.     }
  150.     for(int i=head[G];i;i=edge[i].next) {
  151.     int v=edge[i].to;
  152.     if(!vis[v]) solve(v);
  153.     }
  154. }
  156. int main() {
  157. #ifdef ivorysi
  158.     freopen("f1.in","r",stdin);
  159. #endif
  160.     n=read();k=read();m=read();
  161.     int x,y,z;
  162.     siji(i,1,m) {
  163.     x=read();
  164.     crowd[x]=1;
  165.     }
  166.     xiaosiji(i,1,n) {
  167.     x=read();y=read();z=read();
  168.     addtwo(x,y,z);
  169.     }
  170.     solve(1);
  171.     printf("%d\n",ans);
  172.     return 0;
  173. }

CDQ分治

BZOJ 3262: 陌上花开

Description

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性

Output

包含N行，分别表示评级为0...N-1的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

题解

cdq分治
我们先按s排序，然后进行相同属性的花合成一个
然后分治的时候按照c归并排序，每次用树状数组的算法求在左下角的点有多少个

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 200005
  13. #define esp 1e-8
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,k;
  18. struct node {
  19.     int s,c,m;
  20.     int sum,cnt;
  21.     bool operator < (const node &rhs) const {
  22.     if(s!=rhs.s) return s<rhs.s;
  23.     if(c!=rhs.c) return c<rhs.c;
  24.     return m<rhs.m;
  25.     }
  26.     bool operator == (const node &rhs) const {
  27.     return s==rhs.s && c==rhs.c && m==rhs.m;
  28.     }
  29.     bool operator != (const node &rhs) const {
  30.     return !(*this==rhs);
  31.     } 
  32. }l[MAXN],z[MAXN];
  33. int tr[MAXN],ans[MAXN],tot;
  34. int lowbit(int x) {return x&(-x);}
  35. void insert(int pos,int val) {
  36.     while(pos<=k) {
  37.     tr[pos]+=val;
  38.     pos+=lowbit(pos);
  39.     }
  40. }
  41. int query(int pos) {
  42.     int res=0;
  43.     while(pos>0) {
  44.     res+=tr[pos];
  45.     pos-=lowbit(pos);
  46.     }
  47.     return res;
  48. }
  49. void clear(int pos) {
  50.     while(pos<=k) {
  51.     if(tr[pos]!=0) tr[pos]=0;
  52.     else break;
  53.     pos+=lowbit(pos);
  54.     }
  55. }
  56. void Cdqsolve(int le,int ri) {
  57.     if(le==ri) return;
  58.     int mid=(le+ri)>>1;
  59.     Cdqsolve(le,mid);Cdqsolve(mid+1,ri);
  60.     int L=le,R=mid+1,id=le;
  61.     while(L<=mid && R<=ri) {
  62.     if(z[L].c<=z[R].c) {
  63.         insert(z[L].m,z[L].cnt);
  64.         l[id++]=z[L++];    
  65.     }
  66.     else {
  67.         z[R].sum+=query(z[R].m);
  68.         l[id++]=z[R++];
  69.     }
  70.     }
  71.     while(L<=mid) {
  72.     insert(z[L].m,z[L].cnt);
  73.     l[id++]=z[L++];
  74.     }
  75.     while(R<=ri) {
  76.     z[R].sum+=query(z[R].m);
  77.     l[id++]=z[R++];
  78.     }
  79.     siji(i,le,ri) {
  80.     z[i]=l[i];clear(z[i].m);
  81.     }
  82. }
  83. int main() {
  84. #ifdef ivorysi
  85.     freopen("f1.in","r",stdin);
  86. #endif
  87.     scanf("%d%d",&n,&k);
  88.     siji(i,1,n) {
  89.     scanf("%d%d%d",&l[i].s,&l[i].c,&l[i].m);
  90.     }
  91.     sort(l+1,l+n+1);
  92.     node last=l[1];
  93.     int id=1;
  94.     siji(i,2,n) {
  95.     if(l[i]!=last) {
  96.         z[++tot]=last;
  97.         z[tot].cnt=i-id;
  98.         last=l[i];
  99.         id=i;
  100.     }
  101.     }
  102.     z[++tot]=last;
  103.     z[tot].cnt=n+1-id;
  104.     Cdqsolve(1,tot);
  105.     siji(i,1,tot) {
  106.     ans[z[i].sum+z[i].cnt-1]+=z[i].cnt;
  107.     }
  108.     xiaosiji(i,0,n) {
  109.     printf("%d\n",ans[i]);
  110.     }
  111.     return 0;
  112. }

BZOJ 1176: [Balkan2007]Mokia

Description

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小
接下来每行为一下三种输入之一(不包含引号):
"1 x y a"
"2 x1 y1 x2 y2"
"3"
输入1:你需要把(x,y)(第x行第y列)的格子权值增加a
输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出
输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

Sample Input

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

保证答案不会超过int范围

题解

排序的时候忘记增加操作应该更靠前是真的尴尬…………
我们把查询操作拆成四个矩阵前缀和的加减，然后把这些点按x排序，按照树状数组插入二维平面上的点的算法给每一个询问加上对应的值

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 200005
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int s,w,tot;
  17. ll ans[MAXN],tr[MAXN*10];
  18. struct node {
  19.     int id,op,x,y,pos;
  20.     ll d;
  21.     bool operator < (const node &rhs) const {
  22.     if(x==rhs.x && y==rhs.y) return op<rhs.op;
  23.     if(x!=rhs.x) return x<rhs.x;
  24.     return y<rhs.y;
  25.     }
  26. }qry[MAXN],tmp[MAXN];
  27. int lowbit(int x) {return x&(-x);}
  28. void insert(int pos,ll val) {
  29.     while(pos<=w) {
  30.     tr[pos]+=val;
  31.     pos+=lowbit(pos);
  32.     }
  33. }
  34. ll query(int pos) {
  35.     ll res=0;
  36.     while(pos>0) {
  37.     res+=tr[pos];
  38.     pos-=lowbit(pos);
  39.     }
  40.     return res;
  41. }
  43. void Cdqsolve(int l,int r) {
  44.     if(l==r) return;
  45.     int mid=(l+r)>>1;
  46.     siji(i,l,r) {
  47.     if(qry[i].id<=mid && qry[i].op==1) insert(qry[i].y,qry[i].d);
  48.     if(qry[i].id>mid && qry[i].op==2) ans[qry[i].pos]+=query(qry[i].y)*qry[i].d;
  49.     }
  50.     siji(i,l,r) {
  51.     if(qry[i].id<=mid && qry[i].op==1) insert(qry[i].y,-qry[i].d);
  52.     }
  53.     int idx1=l,idx2=mid+1;
  54.     siji(i,l,r) {
  55.     if(qry[i].id<=mid) tmp[idx1++]=qry[i];
  56.     else tmp[idx2++]=qry[i];
  57.     }
  58.     siji(i,l,r) {
  59.     qry[i]=tmp[i];
  60.     }
  61.     Cdqsolve(l,mid);Cdqsolve(mid+1,r);
  62. }
  63. int main() {
  64. #ifdef ivorysi
  65.     freopen("f1.in","r",stdin);
  66. #endif
  67.     scanf("%d%d",&s,&w);
  68.     int cnt=0,op,x1,y1,a,x2,y2;
  69.     while(scanf("%d",&op)!=EOF) {
  70.     if(op==3) break;
  71.     if(op==1) {
  72.         scanf("%d%d%d",&x1,&y1,&a);
  73.         qry[++cnt]=(node){cnt,op,x1,y1,0,a};
  74.     }
  75.     else {
  76.         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  77.         qry[++cnt]=(node){cnt,op,x2,y2,++tot,1};
  78.         qry[++cnt]=(node){cnt,op,x2,y1-1,tot,-1};
  79.         qry[++cnt]=(node){cnt,op,x1-1,y2,tot,-1};
  80.         qry[++cnt]=(node){cnt,op,x1-1,y1-1,tot,1};
  81.         ans[tot]=(ll)(x2-x1+1)*(y2-y1+1)*s;
  82.     }
  83.     }
  84.     sort(qry+1,qry+cnt+1);
  85.     Cdqsolve(1,cnt);
  86.     siji(i,1,tot) {
  87.     printf("%lld\n",ans[i]);
  88.     }
  89.     return 0;
  90. }

BZOJ 3295: [Cqoi2011]动态逆序对

Description

对于序列A，它的逆序对数定义为满足iAj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4
1
5
3
4
2
5
1
4
2

Sample Output

5
2
2
1

题解

如何转化成对于单个元素求贡献，就是转化一下求删掉这个元素能少几个逆序对
从前和从后分别跑一次树状数组求逆序对就好了

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 100005
  13. #define esp 1e-8
  14. #define pii pair<int,int>
  15. #define fi first
  16. #define se second
  17. #define inf 2000000005
  18. //#define ivorysi
  19. using namespace std;
  20. typedef long long ll;
  21. int n,m;
  22. struct node {
  23.     int num,pos,ti;
  24.     bool operator < (const node &rhs) const {
  25.         return pos<rhs.pos;
  26.     }
  27. }qry[MAXN],tmp[MAXN];
  28. int a[MAXN],pos[MAXN];
  29. ll init,tr[MAXN],ans[MAXN];
  30. bool used[MAXN];
  31. int lowbit(int x) {return x&(-x);}
  32. void insert(int pos,ll val) {
  33.     while(pos<=n) {
  34.         tr[pos]+=val;
  35.         pos+=lowbit(pos);
  36.     }
  37. }
  38. ll query(int pos) {
  39.     ll res=0;
  40.     while(pos>0) {
  41.         res+=tr[pos];
  42.         pos-=lowbit(pos);
  43.     }
  44.     return res;
  45. }
  46. void Cdqsolve(int l,int r) {
  47.     if(l==r) return;
  48.     int mid=(l+r)>>1;
  49.     siji(i,l,r) {
  50.         if(qry[i].ti>mid) insert(qry[i].num,1);
  51.         else ans[qry[i].ti]+=query(n)-query(qry[i].num-1);
  52.     }
  53.     siji(i,l,r) {
  54.         if(qry[i].ti>mid) insert(qry[i].num,-1);
  55.     }
  56.     gongzi(i,r,l) {
  57.         if(qry[i].ti>mid) insert(qry[i].num,1);
  58.         else ans[qry[i].ti]+=query(qry[i].num);
  59.     }
  60.     siji(i,l,r) {
  61.         if(qry[i].ti>mid) insert(qry[i].num,-1);
  62.     }
  63.     int idx1=l,idx2=mid+1;
  64.     siji(i,l,r) {
  65.         if(qry[i].ti<=mid) tmp[idx1++]=qry[i];
  66.         else tmp[idx2++]=qry[i];
  67.     }
  68.     siji(i,l,r) {
  69.         qry[i]=tmp[i];
  70.     }
  71.     Cdqsolve(l,mid);Cdqsolve(mid+1,r);
  72. }
  73. int main() {
  74. #ifdef ivorysi
  75.     freopen("f1.in","r",stdin);
  76. #endif
  77.     scanf("%d%d",&n,&m);
  78.     siji(i,1,n) {
  79.         scanf("%d",&a[i]);
  80.         pos[a[i]]=i;
  81.     }
  82.     int x,cnt=m;
  83.     siji(i,1,m) {
  84.         scanf("%d",&x);
  85.         qry[i].num=x;
  86.         qry[i].pos=pos[x];
  87.         qry[i].ti=i;
  88.         used[x]=1;
  89.     }
  90.     siji(i,1,n) {
  91.         if(!used[i]) {
  92.             qry[++cnt].num=i;
  93.             qry[cnt].pos=pos[i];
  94.             qry[cnt].ti=cnt;
  95.         }
  96.     }
  97.     gongzi(i,n,1) {
  98.         init+=query(a[i]);
  99.         insert(a[i],1);
  100.     }
  101.     memset(tr,0,sizeof(tr));
  102.     sort(qry+1,qry+n+1);
  103.     Cdqsolve(1,n);
  104.     siji(i,1,m) {
  105.         printf("%lld\n",init);
  106.         init-=ans[i];
  107.     }
  108. }

BZOJ 2716 天使玩偶

给出n个点
m次操作
1 x y 表示再插入一个点x y
2 x y 表示询问离x y最近的点的距离

题解

我们可以先拆绝对值的式子，这样我们强制让每个点在这个点左下角，剩下的三种情况可以通过翻转获得
我们记录插入点x+y根据y来存储的最大值，每次询问去查询y值小于询问点y值的最大值
套用cdq分治的板子

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 500005
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int n,m;
  17. struct node {
  18.     int id,op,x,y,pos;
  19.     bool operator < (const node &rhs) const{
  20.     if(x==rhs.x && y==rhs.y) return op<rhs.op;
  21.     if(x!=rhs.x) return x<rhs.x;
  22.     return y<rhs.y;
  23.     }
  24. }qry[MAXN*2],tmp[MAXN*2];
  25. int ans[MAXN*2],tot;
  26. int maxsize=1000005;
  27. int tr[2000010];
  28. int lowbit(int x) {return x&(-x);}
  29. void insert(int pos,int val) {
  30.     while(pos<=maxsize) {
  31.     tr[pos]=max(tr[pos],val);
  32.     pos+=lowbit(pos);
  33.     }
  34. }
  35. int query(int pos) {
  36.     int res=0;
  37.     while(pos>0) {
  38.     res=max(res,tr[pos]);
  39.     pos-=lowbit(pos);
  40.     }
  41.     return res;
  42. }
  43. void clear(int pos) {
  44.     while(pos<=maxsize) {
  45.     tr[pos]=0;
  46.     pos+=lowbit(pos);
  47.     }
  48. }
  49. void Cdqsolve(int l,int r) {
  50.     if(l==r) return;
  51.     int mid=(l+r)>>1;
  52.     siji(i,l,r) {
  53.     if(qry[i].id<=mid && qry[i].op==1) {
  54.         insert(qry[i].y,qry[i].y+qry[i].x);
  55.     }
  56.     if(qry[i].id>mid && qry[i].op==2) {
  57.         int t=query(qry[i].y);
  58.         if(t!=0) {
  59.         if(qry[i].x+qry[i].y-t<0) {
  60.             printf("--------\n");
  61.             printf("%d\n",t);
  62.             printf("%d %d %d\n",i,qry[i].x,qry[i].y);
  63.             printf("--------\n");
  64.         }
  65.         ans[qry[i].pos]=min(ans[qry[i].pos],qry[i].x+qry[i].y-t);
  66.         }
  67.     }
  68.     }
  69.     int idx1=l,idx2=mid+1;
  70.     siji(i,l,r) {
  71.     if(qry[i].id<=mid && qry[i].op==1) {
  72.         clear(qry[i].y);
  73.     }
  74.     if(qry[i].id<=mid) tmp[idx1++]=qry[i];
  75.     else tmp[idx2++]=qry[i];
  76.     }
  77.     siji(i,l,r) qry[i]=tmp[i];
  78.     Cdqsolve(l,mid);
  79.     Cdqsolve(mid+1,r);
  80. }
  81. int main() {
  82. #ifdef ivorysi
  83.     freopen("f1.in","r",stdin);
  84. #endif
  85.     scanf("%d%d",&n,&m);
  86.     int t,x,y;
  87.     siji(i,1,n) {
  88.     scanf("%d%d",&x,&y);
  89.     ++x;++y;
  90.     qry[i]=(node){i,1,x,y,0};
  91.     }
  92.     siji(i,1,m) {
  93.     scanf("%d%d%d",&t,&x,&y);
  94.     ++x;++y;
  95.     if(t==1) {
  96.         qry[i+n]=(node){i+n,1,x,y,0};
  97.     }
  98.     else {
  99.         qry[i+n]=(node){i+n,2,x,y,++tot};
  100.         ans[tot]=0x7fffffff;
  101.     }
  102.     }
  103.     sort(qry+1,qry+n+m+1);
  104.     Cdqsolve(1,n+m);
  105.     siji(i,1,n+m) {
  106.     qry[i].y=maxsize-qry[i].y;
  107.     }
  108.     sort(qry+1,qry+n+m+1);
  109.     Cdqsolve(1,n+m);
  110.     siji(i,1,n+m) {
  111.     qry[i].x=maxsize-qry[i].x;
  112.     }
  113.     sort(qry+1,qry+n+m+1);
  114.     Cdqsolve(1,n+m);
  115.     siji(i,1,n+m) {
  116.     qry[i].y=maxsize-qry[i].y;
  117.     }
  118.     sort(qry+1,qry+n+m+1);
  119.     Cdqsolve(1,n+m);
  120.     siji(i,1,tot) {
  121.     printf("%d\n",ans[i]);
  122.     }
  123.     return 0;
  124. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注