题解

题目分析

这是一道基于几何和树状数组的题目，需要计算矩形区域内经过的点的数量。

解题思路

1. 问题建模

• 在 $n \times m$ 的网格中，有一个点按照指令移动 $k$ 步
• 需要回答 $q$ 个查询，每个查询问矩形区域内经过的点的数量
• 使用容斥原理和树状数组优化计算

2. 移动处理

• 根据指令 E/W/S/N 更新坐标
• 记录所有经过的点：ins(x, y) 函数
• 维护边界信息：mnx, mxx, mny, mxy

3. 容斥原理

• 使用四个树状数组：t1, t2, t3, t4
• 分别处理不同的几何区域
• 通过容斥原理计算矩形内点的数量

4. 树状数组

• 实现单点更新：upd(x, f)
• 实现区间查询：query(l, r)
• 使用位运算优化：x += x & -x

5. 查询处理

• 预处理答案：$(\text{xx}-\text{x}+1) \times (\text{yy}-\text{y}+1) - \text{边界项}$
• 使用四个树状数组分别计算不同区域
• 最终答案：$res[i] = \text{基础答案} + \text{容斥项}$

时间复杂度

$O(k \log m + q \log m)$，其中 $k$ 为移动步数，$q$ 为查询次数，$m$ 为网格宽度。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,k,q,sx,sy,res[100009];
int mnx=200009,mxx=0,mny=200009,mxy=0;
vector<int> de1[200009],de2[200009],de3[200009],de4[200009];
vector<array<int,4> > qr1[200009],qr2[200009],qr3[200009],qr4[200009];
struct fenwick{
	int c[200009];
	void upd(int x,int f){while(x<=m)c[x]+=f,x+=x&-x;}
	int query(int x){int f=0;while(x)f+=c[x],x-=x&-x;return f;}
	int query(int l,int r){return query(r)-query(l-1);}
}t1,t2,t3,t4;
void ins(int x,int y){
	mnx=min(mnx,x);
	mxx=max(mxx,x);
	mny=min(mny,y);
	mxy=max(mxy,y);
	de1[x].push_back(y);
	de2[x].push_back(y);
	if(x>1)de2[x-1].push_back(y);
	de3[x].push_back(y);
	if(y>1)de3[x].push_back(y-1);
	de4[x].push_back(y);
	if(x>1)de4[x-1].push_back(y);
	if(y>1)de4[x].push_back(y-1);
	if(x>1)if(y>1)de4[x-1].push_back(y-1);
}
void adq(int x,int y,int xx,int yy,int tp,int id,vector<array<int,4> > *f){
	f[x-1].push_back({y,yy,-tp,id});
	f[xx].push_back({y,yy,tp,id});
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k>>q>>sx>>sy;
	ins(sx,sy);
	for(int i=1;i<=k;i++){
		char c;cin>>c;
		if(c=='E')sy++;
		if(c=='W')sy--;
		if(c=='S')sx++;
		if(c=='N')sx--;
		ins(sx,sy);
	}
	for(int i=1;i<=q;i++){
		int x,y,xx,yy;cin>>x>>y>>xx>>yy;
		res[i]=(xx-x+1)*(yy-y+1)-(xx-x)*(yy-y+1)-(xx-x+1)*(yy-y)+(xx-x)*(yy-y);
		res[i]+=(x<mnx&&xx>mxx&&y<mny&&yy>mxy);
		adq(x,y,xx,yy,-1,i,qr1);
		adq(x,y,xx-1,yy,1,i,qr2);
		adq(x,y,xx,yy-1,1,i,qr3);
		adq(x,y,xx-1,yy-1,-1,i,qr4);
	}
	for(int i=1;i<=n;i++){
		sort(de1[i].begin(),de1[i].end());
		de1[i].resize(unique(de1[i].begin(),de1[i].end())-de1[i].begin());
		for(int x:de1[i])t1.upd(x,1);
		sort(de2[i].begin(),de2[i].end());
		de2[i].resize(unique(de2[i].begin(),de2[i].end())-de2[i].begin());
		for(int x:de2[i])t2.upd(x,1);
		sort(de3[i].begin(),de3[i].end());
		de3[i].resize(unique(de3[i].begin(),de3[i].end())-de3[i].begin());
		for(int x:de3[i])t3.upd(x,1);
		sort(de4[i].begin(),de4[i].end());
		de4[i].resize(unique(de4[i].begin(),de4[i].end())-de4[i].begin());
		for(int x:de4[i])t4.upd(x,1);
		for(auto p:qr1[i])res[p[3]]+=p[2]*t1.query(p[0],p[1]);
		for(auto p:qr2[i])res[p[3]]+=p[2]*t2.query(p[0],p[1]);
		for(auto p:qr3[i])res[p[3]]+=p[2]*t3.query(p[0],p[1]);
		for(auto p:qr4[i])res[p[3]]+=p[2]*t4.query(p[0],p[1]);
	}
	for(int i=1;i<=q;i++)cout<<res[i]<<endl;
	return 0;
}