luogu3755 [CQOI2017]老C的任务

扫描线水题。
#include <algorithm>

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, m, dx[300005], dy[300005], cntx, cnty, cnt, uu, vv, ww, aa, bb;

ll ans[100005], c[300005];

struct Node{

	int idd, val, xxx, yyy;

}nd[500005];

bool cmp(Node x, Node y){

	if(x.xxx==y.xxx)	return x.idd<y.idd;

	else	return x.xxx<y.xxx;

}

int lb(int x){

	return x&-x;

}

void add(int pos, int w){

	for(int i=pos; i<=cnty; i+=lb(i))

		c[i] += w;

}

ll query(int pos){

	ll re=0;

	for(int i=pos; i; i-=lb(i))

		re += c[i];

	return re;

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=n; i++){

		scanf("%d %d %d", &uu, &vv, &ww);

		nd[++cnt] = (Node){0, ww, uu, vv};

		dx[++cntx] = uu;

		dy[++cnty] = vv;

	}

	for(int i=1; i<=m; i++){

		scanf("%d %d %d %d", &uu, &vv, &aa, &bb);

		uu--; vv--;

		dx[++cntx] = uu; dx[++cntx] = aa;

		dy[++cnty] = vv; dy[++cnty] = bb;

		nd[++cnt] = (Node){i, 1, uu, vv};

		nd[++cnt] = (Node){i, -1, uu, bb};

		nd[++cnt] = (Node){i, -1, aa, vv};

		nd[++cnt] = (Node){i, 1, aa, bb};

	}

	sort(dx+1, dx+1+cntx);

	sort(dy+1, dy+1+cnty);

	cntx = unique(dx+1, dx+1+cntx) - (dx + 1);

	cnty = unique(dy+1, dy+1+cnty) - (dy + 1);

	for(int i=1; i<=cnt; i++){

		nd[i].xxx = lower_bound(dx+1, dx+1+cntx, nd[i].xxx) - dx;

		nd[i].yyy = lower_bound(dy+1, dy+1+cnty, nd[i].yyy) - dy;

	}

	sort(nd+1, nd+1+cnt, cmp);

	for(int i=1; i<=cnt; i++){

		if(!nd[i].idd)	add(nd[i].yyy, nd[i].val);

		else	ans[nd[i].idd] += query(nd[i].yyy) * nd[i].val;

	}

	for(int i=1; i<=m; i++)

		printf("%lld\n", ans[i]);

	return 0;

}
巴特西

luogu3755 [CQOI2017]老C的任务

最新文章

热门文章
