做360网站中保存的图片存在哪里,广告设计公司制作,宁波网站搜索排名,网站规划建设案例一道CDQ分治的模板题#xff0c;然而我De了一上午Bug...... 按时间分成左右两半#xff0c;按x坐标排序然后把y坐标丢到树状数组里#xff0c;扫一遍遇到左边的就add,遇到右边的query 几个弱智出了bug的点#xff0c; 一是先分了左右两半再排序#xff0c;保证的是这次的左…一道CDQ分治的模板题然而我De了一上午Bug...... 按时间分成左右两半按x坐标排序然后把y坐标丢到树状数组里扫一遍遇到左边的就add,遇到右边的query 几个弱智出了bug的点 一是先分了左右两半再排序保证的是这次的左右是上次没有计算过的贡献 for(int il;ir;i) qs[i].k(imid);sort(qsl,qsr1,cmp2); 然后时间的先后是因为一开始就是按时间排好序的已经保证了。 二是矩阵的一个经典的套路就是拆成四部分差分查询。 三是很智障的树状数组要注意y0的情况 四是比较重要的比较的时候条件要加充分之前写陌上花开也出现了这个问题一维还是两维相同就不管了会爆炸。。。一定要考虑清楚所有会影响的维都要加入排序条件中 bool cmp2(const nodea,const nodeb) {return a.xb.x||(a.xb.x(a.yb.y||(a.yb.ybo[a.id]bo[b.id])));
} 还有数组大小要开够在下RE好像大半都是数组问题。。 //Twenty
#includecstdio
#includecstdlib
#includeiostream
#includealgorithm
#includecmath
#includecstring
#includequeue
#includevector
#define mid ((lr)1)
using namespace std;
const int maxn200000299;
const int maxw200000029;
int tot,s,w,opt,x,y,x2,y2,a,sg[maxw],bo[maxn],ans,cnt;
struct node{int x,y,v,id,sum,k;node(){sum0;};node(int x,int y,int v,int id):x(x),y(y),v(v),id(id){sum0;}
}qs[maxn];
bool cmp1(const nodea,const nodeb) {return a.idb.id;
}
bool cmp2(const nodea,const nodeb) {return a.xb.x||(a.xb.x(a.yb.y||(a.yb.ybo[a.id]bo[b.id])));//!!!!!!!
}
void add(int x,int v) {for(int ix;iw;i(i(-i))) sg[i]v;
}
int qry(int x) {int res0;for(int ix;i0;i-(i(-i))) ressg[i];return res;
}
void solve(int l,int r) {if(lr) return ;solve(l,mid); solve(mid1,r);for(int il;ir;i) qs[i].k(imid);sort(qsl,qsr1,cmp2);for(int il;ir;i) {if(bo[qs[i].id]qs[i].k) {if(qs[i].y) qs[i].sumqry(qs[i].y);}else if(!bo[qs[i].id]!qs[i].k) {if(qs[i].y ) add(qs[i].y,qs[i].v);}}for(int il;ir;i) if(!bo[qs[i].id]!qs[i].k) {if(qs[i].y) add(qs[i].y,-qs[i].v); }
}
int main()
{scanf(%d%d,s,w);for(;;) {scanf(%d,opt); if(opt3) break;if(opt1) {scanf(%d%d%d,x,y,a);qs[tot]node(x,y,a,tot);}else {scanf(%d%d%d%d,x,y,x2,y2);qs[tot]node(x-1,y-1,1,tot);qs[tot]node(x-1,y2,-1,tot-1);qs[tot]node(x2,y-1,-1,tot-2);qs[tot]node(x2,y2,1,tot-3);bo[tot-3]1;//是询问 }}solve(1,tot);sort(qs1,qstot1,cmp1);for(int i1;itot;i) if(bo[qs[i].id]){cnt;ansqs[i].sum*qs[i].v;if(cnt4) {printf(%d\n,ans);ans0,cnt0;} }return 0;
} 1176: [Balkan2007]Mokia 吐槽一句为什么都是权限题呀。。转载于:https://www.cnblogs.com/Achenchen/p/7477567.html
