第二回 アルゴリズム実技検定 : N - ビルの建設

これは典型かな…。
https://atcoder.jp/contests/past202004-open/tasks/past202004_n

問題

２次元座標上に、N個の正方形領域が指定される。
それぞれの領域にはコストが指定される。

加えてQ個の点が指定されるので、それぞれその点を含む正方形領域のコストの総和を答えよ。

解法

平面走査で解く。
Y座標を圧縮しておき、座標ごとのコストの総和を管理しよう。
X座標順に、正方形領域の出入りに応じて座標ごとのコストを更新する。
また、クエリに対し、Y座標に応じたコストを答える。

int N,Q;
ll X[101010],Y[101010],D[101010],C[101010];
int AX[101010],AY[101010];
vector<ll> Ys;
vector<pair<int,int>> ev;

//さらに短縮
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;
ll ret[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>D[i]>>C[i];
		Ys.push_back(Y[i]);
		Ys.push_back(Y[i]+D[i]);
		ev.push_back({X[i],i});
		ev.push_back({X[i]+D[i],N+Q+i});
	}
	FOR(i,Q) {
		cin>>AX[i]>>AY[i];
		Ys.push_back(AY[i]);
		ev.push_back({AX[i],i+N});
	}
	Ys.push_back(-1<<30);
	sort(ALL(Ys));
	sort(ALL(ev));
	FORR(e,ev) {
		x=e.second;
		if(x<N || x>=N+Q) {
			if(x>=N+Q) x-=N+Q;
			int y1=lower_bound(ALL(Ys),Y[x])-Ys.begin();
			int y2=lower_bound(ALL(Ys),Y[x]+D[x])-Ys.begin();
			if(e.second<N) bt.add(y1,C[x]),bt.add(y2+1,-C[x]);
			else bt.add(y1,-C[x]),bt.add(y2+1,C[x]);
		}
		else {
			x-=N;
			y=lower_bound(ALL(Ys),AY[x])-Ys.begin();
			ret[x]=bt(y);
		}
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

Mより楽だな。