在ps做网站分辨率96可以吗,公司建设包括哪些方面,青羊区区建设局网站,给网站app做后台的公司题目这么说的#xff1a; 进行如下3种类型操作#xff1a;1#xff09;D L R(1 L R 1000000000) 增加一条线段[L,R]2#xff09;C i (1-base) 删除第i条增加的线段#xff0c;保证每条插入线段最多插入一次#xff0c;且这次删除操作一定合法3) Q L R(1 进行如下3种类型操作1D L R(1 L R 1000000000) 增加一条线段[L,R]2C i (1-base) 删除第i条增加的线段保证每条插入线段最多插入一次且这次删除操作一定合法3) Q L R(1 L R 1000000000) 查询目前存在的线段中有多少条线段完全包含[L,R]这个线段线段X被线段Y完全包含即LY LX RX RY) 初学CDQ分治是看了Balkan OI 2007 Mokia那题的解法。两题类似这题做法也不难想出 每次对操作的区间进行分治时统计左半边更新操作对右半边查询操作的影响影响的前提是更新操作的L小于等于查询操作的L且R要大于等于查询的R这个通过一开始把L按从小到大排序分治时便可从大到小遍历同时用线段树维护R出现次数即可。其实我一开始看错题以为询问的是有几条线段包含在给定区间里面写完后发现才样例过不了。。不过改一下就好了然后1A感觉还是不错的。 1 #includecstdio2 #includecstring3 #includealgorithm4 using namespace std;5 6 int tree[2222222],N,x,y;7 void update(int i,int j,int k){8 if(ij){9 tree[k]y;10 return;11 }12 int midij1;13 if(xmid) update(i,mid,k1);14 else update(mid1,j,k1|1);15 tree[k]tree[k1]tree[k1|1];16 }17 int query(int i,int j,int k){18 if(xi jy){19 return tree[k];20 }21 int midij1,res0;22 if(xmid) resquery(i,mid,k1);23 if(ymid) resquery(mid1,j,k1|1);24 return res;25 }26 27 struct Query{28 int idx,type,anspos;29 int x,y;30 bool operator(const Query q)const{31 return xq.x;32 }33 }que[111111],tmp[111111];34 35 int ans[111111];36 37 void cdq(int l,int r){38 if(lr) return;39 int midlr1,il,jmid1;40 for(int kl; kr; k){41 if(que[k].idxmid) tmp[i]que[k];42 else tmp[j]que[k];43 }44 for(int kl; kr; k) que[k]tmp[k];45 46 for(imid1,jl; ir; i){47 if(que[i].type!3) continue;48 for( ; jmid que[j].xque[i].x; j){49 if(que[j].type3) continue;50 xque[j].y; y(que[j].type1) ? 1 : -1;51 update(0,N-1,1);52 }53 xque[i].y; yN-1;54 ans[que[i].anspos]query(0,N-1,1);55 }56 for(il; ij; i){57 if(que[i].type3) continue;58 xque[i].y; y(que[i].type1) ? -1 : 1;59 update(0,N-1,1);60 }61 cdq(l,mid); cdq(mid1,r);62 }63 64 int segx[111111],segy[111111],sn;65 int point[222222],pn;66 int main(){67 char op;68 int n,a,b;69 while(~scanf(%d,n)){70 int cnt0;71 memset(ans,0,sizeof(ans));72 sn0; pn0;73 for(int i0; in; i){74 scanf( %c,op);75 if(opD){76 scanf(%d%d,a,b);77 segx[sn]a; segy[sn]b;78 point[pn]a; point[pn]b;79 que[i].idxi; que[i].type1; que[i].xa; que[i].yb;80 }else if(opC){81 scanf(%d,a);82 que[i].idxi; que[i].type2; que[i].xsegx[a]; que[i].ysegy[a];83 }else{84 scanf(%d%d,a,b);85 point[pn]a; point[pn]b;86 que[i].idxi; que[i].type3; que[i].xa; que[i].yb; que[i].ansposcnt;87 }88 }89 90 sort(point,pointpn);91 pnunique(point,pointpn)-point;92 for(N1; Npn; N1);93 94 for(int i0; in; i){95 que[i].xlower_bound(point,pointpn,que[i].x)-point;96 que[i].ylower_bound(point,pointpn,que[i].y)-point;97 }98 99 sort(que,quen);
100 cdq(0,n-1);
101
102 for(int i1; icnt; i){
103 printf(%d\n,ans[i]);
104 }
105 }
106 return 0;
107 } 转载于:https://www.cnblogs.com/WABoss/p/5701844.html
