牛客2019多校联盟Day7 Fine the median
题意： 每次给数组插入区间[Li,Ri] 内的所有数，每操作一次查询中位数。
遇到这题真的算是巧合，然而就是这种冥冥之中的缘分，给了我线段树的一个全新的思想。
这题与以往的线段树做法有所不同，常规的线段树题目，可能就是一个点区间代表一个数据，然后找个区间最大值什么的。
这种很显而易见的，对吧？因为点区间代表了一个点，仅仅是一个点，所以做起来比较容易。
而今天这题十分有趣。它的点区间代表的是一个区间。
比如这题，我们去怎么解决呢？
对于更新，所有要加入的区间，我们先离散化。比如我们要加【1，3】【3，6】 .去重之后的数组就是【1,3,6】，之后处理【1，3】这个操作的时候，直接lower_bound定位他在离散数组里面的那个位置，以这个位置做为线段树的建树和后续查询的依据。
对于查询，我们要定义一个数组代表线段树里面的某个区间加了多少个数。如果左子区间的个数大于中位数所在的位置，就去左子区间；如果右子区间的个数大于中位数所在的位置，那么我们就把中位数所在的位置减去左子区间的个数。
其实这题妙在线段树与离散化数组构成的联系，线段树的区间就是刚好对应了离散数组的位置。详情看代码
#include <bits/stdc++.h> #define maxn 400005 using namespace std; typedef long long ll; int i,n,zuo,you; ll sum,x[maxn],y[maxn],A1,A2,B1,B2,C1,C2,M1,M2,a[maxn*6],lazy[maxn*6],G[maxn*2],L[maxn],R[maxn]; void push_up(int num) { a[num]=a[num*2]+a[num*2+1]; } void push_down(int l,int r,int num) { if (lazy[num]==0) return; int mid=(l+r)/2; lazy[num*2]+=lazy[num]; lazy[num*2+1]+=lazy[num]; a[num*2]+=(G[mid+1]-G[l])*lazy[num]; a[num*2+1]+=(G[r+1]-G[mid+1])*lazy[num]; lazy[num]=0; } void upgrade(int l,int r,int num) { if (zuo<=l && r<=you) { lazy[num]+=1; a[num]+=G[r+1]-G[l]; return; } push_down(l,r,num); int mid=(l+r)/2; if (mid>=zuo) upgrade(l,mid,num*2); if (mid<you) upgrade(mid+1,r,num*2+1); push_up(num); } ll query(int l,int r,int num,ll sum) { if (l==r) { int ti=a[num]/(G[r+1]-G[l]); return G[l]+(sum-1)/ti; } push_down(l,r,num); int mid=(l+r)/2; if (a[num*2]>=sum) return query(l,mid,num*2,sum); else return query(mid+1,r,num*2+1,sum-a[num*2]); } int main() { cin>>n; scanf("%lld%lld%lld%lld%lld%lld",&x[1],&x[2],&A1,&B1,&C1,&M1); scanf("%lld%lld%lld%lld%lld%lld",&y[1],&y[2],&A2,&B2,&C2,&M2); for (i=3;i<=n;i++) { x[i]=(A1*x[i-1]+B1*x[i-2]+C1)%M1; y[i]=(A2*y[i-1]+B2*y[i-2]+C2)%M2; } for (i=1;i<=n;i++) { L[i]=min(x[i],y[i])+1; R[i]=max(x[i],y[i])+1+1; G[i]=L[i]; G[i+n]=R[i]; } sort(G+1,G+1+2*n); int element=unique(G+1,G+1+2*n)-G-1; for (i=1;i<=n;i++) { sum+=R[i]-L[i]; zuo=lower_bound(G+1,G+1+element,L[i])-G; you=lower_bound(G+1,G+1+element,R[i])-G-1; upgrade(0,element,1); printf("%lld ",query(0,element,1,(sum+1)/2)); } return 0; }
CF round 624 F
看到这题的时候就感觉有些熟悉，但是树状数组写的很少，于是一开始就想着用线段树去解决，然后看了看数据范围，感觉线段树很有可能会爆，于是匆匆收场。
其实当时我还想着一个比较傻b的问题，A点在B点后面，速度比B要大，相隔距离最短的时候是多少米。对，没错，这道高中物理送分题，我竟然想了一段时间。枯了
我们可以看到有两种情况
一个点在另一个点的后面，速度比它小，那么相隔距离最短的时候就是0秒的时候
一个点在另一个点的后面，速度比它大，那么它们两个一定能相遇！
所以我们把点的坐标、速度分别从小到大排序。我们这里不用查重，因为查重之后就找不到对应的位置了。
以点的大小为依据，又分两种情况
一个是速度为负，一个是速度为正，对于两点之间速度相反的点，我们直接相加和他们的初始的距离。这里可能会有疑问？如果当前处理的点速度为正，下一个要循环的点速度为负且这个点在当前点的右边，那么它们不会相遇吗？这里我们进行一个处理，对于速度为负的点，我们只处理与速度为负的其他点的关系；对于速度为正的点，我们就全部处理。
那么速度相向的问题解决了，速度方向相同呢？
如果0s的时候是最佳答案，我们把当前点的速度就存在树状数组里，我们在下一个点的处理，把两点之间距离加上。
我们要清楚这里是标量之间比较大小，所以数字小的速度肯定会被数字大的速度累加到，累加这个过程就有点前缀和的味道，具体看程序。
#include <bits/stdc++.h> typedef long long ll; using namespace std; struct node { int x,v; }; const int N = 2e5 + 10; node a[N]; int n,i,v[N]; ll z[N], f[N], zhsum[N], fusum[N],num,ans; bool cmp(node x,node y) { return x.x<y.x; } int lowbit(int x) { return x & (-x); } ll sum(int x,ll d[]) { ll cnt=0; while (x) { cnt+=d[x]; x-=lowbit(x); } return cnt; } void add(int x,int k,ll d[]) { while (x<N) { d[x]+=k; x+=lowbit(x); } } int main() { scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i].x); for (i=1;i<=n;i++) { scanf("%d",&a[i].v); v[i]=a[i].v; } sort(v+1,v+1+n); sort(a+1,a+1+n,cmp); for (i=1;i<=n;i++) { if (a[i].v<0) { num=lower_bound(v+1,v+1+n,a[i].v)-v; ans+=sum(num,fusum)*a[i].x-sum(num,f); add(num,a[i].x,f); add(num,1,fusum); } else { num=lower_bound(v+1,v+1+n,a[i].v)-v; ans+=sum(N-1,fusum)*a[i].x-sum(N-1,f); ans+=sum(num,zhsum)*a[i].x-sum(num,z); add(num,a[i].x,z); add(num,1,zhsum); } } cout<<ans<<endl; return 0; }