Bzoj4822 [Cqoi2017]老C的任务

 2023-09-05 阅读 223 评论 0

摘要:同样没题面 写完以后的感想是:我™都干了点啥。 正解是扫描线+树状数组 Bzoj1935 [SHOI2007]Tree 园丁的烦恼 ↑差不多是原题。 然而……我写了K-Dtree 思维江化啊 幸好Bzoj的评测是计算总时间而不是单点时间的,让我得以卡过去233 1 #include<algorit

同样没题面

 

 

写完以后的感想是:我™都干了点啥。

正解是扫描线+树状数组

Bzoj1935 [SHOI2007]Tree 园丁的烦恼

↑差不多是原题。

 

然而……我写了K-Dtree

思维江化啊

幸好Bzoj的评测是计算总时间而不是单点时间的,让我得以卡过去233

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<vector>
  7 #define LL long long
  8 using namespace std;
  9 const int INF=1e9+7;
 10 const int mxn=100011;
 11 LL read(){
 12     LL x=0,f=1;char ch=getchar();
 13     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 14     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 15     return x*f;
 16 }
 17 int n,m;
 18 struct node{
 19     int l,r;
 20     int d[2];
 21     int mn[2],mx[2];
 22     LL v,smm;
 23 }t[mxn];
 24 int nowD,rot=0;
 25 inline int cmp(const node a,const node b){
 26     return a.d[nowD]<b.d[nowD];
 27 }
 28 LL ans=0;
 29 int qx1,qy1,qx2,qy2;
 30 void pushup(int rt,int x){
 31     t[rt].mn[0]=min(t[rt].mn[0],t[x].mn[0]);
 32     t[rt].mn[1]=min(t[rt].mn[1],t[x].mn[1]);
 33     t[rt].mx[0]=max(t[rt].mx[0],t[x].mx[0]);
 34     t[rt].mx[1]=max(t[rt].mx[1],t[x].mx[1]);
 35     return;
 36 }
 37 bool in(int rt){
 38     return qx1<=t[rt].mn[0] && t[rt].mx[0]<=qx2
 39             && qy1<=t[rt].mn[1] && t[rt].mx[1]<=qy2;
 40 }
 41 bool out(int rt){
 42     return qx2<t[rt].mn[0] || qy2<t[rt].mn[1] 
 43             || qx1>t[rt].mx[0] || qy1>t[rt].mx[1];
 44 }
 45 int Build(int l,int r,int D){
 46     if(l>r)return 0;
 47     int mid=(l+r)>>1;
 48     nowD=D;
 49     nth_element(t+l,t+mid,t+r+1,cmp);
 50     t[mid].l=Build(l,mid-1,D^1);
 51     if(t[mid].l){
 52         pushup(mid,t[mid].l);
 53     }
 54     t[mid].r=Build(mid+1,r,D^1);
 55     if(t[mid].r){
 56         pushup(mid,t[mid].r);
 57     }
 58     t[mid].smm=t[mid].v+t[t[mid].l].smm+t[t[mid].r].smm;
 59 /*    printf("#%d: l:%d r:%d v:%lld smm:%lld\n",
 60             mid,t[mid].l,t[mid].r,t[mid].v,t[mid].smm);*/
 61     return mid;
 62 }
 63 void query(int rt){
 64     if(!rt)return;
 65     if(out(rt)){
 66         return;
 67     }
 68     if(in(rt)){
 69         ans+=t[rt].smm;
 70         return;
 71     }
 72     if(qx1<=t[rt].d[0] && t[rt].d[0]<=qx2 && 
 73         qy1<=t[rt].d[1] && t[rt].d[1]<=qy2)
 74             ans+=t[rt].v;
 75 //    printf("fin\n");
 76     if(t[rt].l)query(t[rt].l);
 77     if(t[rt].r)query(t[rt].r);
 78     return;
 79 }
 80 int main(){
 81 //    freopen("task.in","r",stdin);
 82 //    freopen("task.out","w",stdout);
 83     int i,j,x,y,w;
 84     n=read();m=read();
 85     t[0].mn[0]=INF;t[0].mx[0]=-INF;
 86     t[0].mn[1]=INF;t[0].mx[1]=-INF;
 87     t[0].smm=t[0].v=0;
 88     for(i=1;i<=n;i++){
 89         x=read();y=read();w=read();
 90         t[i].d[0]=x; t[i].d[1]=y; t[i].v=w;
 91         t[i].mn[0]=t[i].mx[0]=x;
 92         t[i].mn[1]=t[i].mx[1]=y;
 93     }
 94     rot=Build(1,n,0);
 95     while(m--){
 96         qx1=read();qy1=read();
 97         qx2=read();qy2=read();
 98         ans=0;
 99         query(rot);
100         printf("%lld\n",ans);
101     }
102     return 0;    
103 }

 

转载于:https://www.cnblogs.com/SilverNebula/p/6701473.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/1/741.html

下一篇:LNMP快速安装

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息