BZOJ4223 : Tourists

将位置划分成$O(m)$段区间，每段最早被阻挡的时间可以用堆维护。

那么每段区间对询问的贡献独立，扫描线处理即可。

时间复杂度$O(m\log m)$。

#include<cstdio>#include<algorithm>#include<queue>using namespace std;typedef pair<int,int>P;const int N=100010;int n,m,i,x,y,z,cnt,tot,sum,k;bool del[N];priority_queue<P>q;struct E{int x,y,p;E(){}E(int _x,int _y,int _p){x=_x,y=_y,p=_p;}}e[N<<1],a[N<<2];inline bool cmp(const E&a,const E&b){return a.x<b.x;}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y){while(!q.empty())if(del[q.top().second])q.pop();else break;if(q.empty())return;int t=-q.top().first;a[++tot]=E(t-y,y-t,1);a[++tot]=E(t-x,t-x,-1);}int main(){read(m),read(n);for(i=1;i<=n;i++){read(x),read(y),read(z);e[++cnt]=E(x,z,i);e[++cnt]=E(y,z,-i);}sort(e+1,e+cnt+1,cmp);for(i=1;i<=cnt;i++){if(i>1&&e[i].x>e[i-1].x)add(e[i-1].x,e[i].x);if(e[i].p>0)q.push(P(-e[i].y,e[i].p));else del[-e[i].p]=1;}sort(a+1,a+tot+1,cmp);for(i=1;m--;printf("%d\n",x*k+sum))for(read(x);i<=tot&&a[i].x<=x;i++)sum+=a[i].y,k+=a[i].p;return 0;}