icontofig | 发布于 2019-09-02 23:23:58 | 阅读量 654 | 思维题 扫描线 树状数组

## 题解

x = x − n/2 − 1
y = y  - n /2 - 1；
t = max(abs(x),abs(y))； //确定该点在第几圈螺旋
if(x >= y)ans = n ∗ n −4∗ t ∗ t −2∗ t − x − y;//在向右与向上的路线上

else ans = n ∗ n −4∗ t ∗ t +2∗ t + x + y;//在向左与向下的路线上

(下面这部分代码是队友写的，我不是很清楚他的思路)

## 代码

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(int x, int y, int n){
int layer = min(min(x, y), n - max(x, y) + 1);
if ((layer << 1) > n){
return 1LL * n * n;
}
long long st = 1LL * n * n - 1LL * (n - (layer << 1) + 2) * (n - (layer << 1) + 2) + 1;
if (x >= y){
return st + ((n - layer) << 1) + 2 - x - y;
}
return st + ((n - (layer << 1) + 1) << 1) + x + y - (layer << 1);
}
const int maxn = 1e6+5;
const int maxm = 1e5 + 5;
struct quest{
int x,y;
int flag;
int id;
}e[maxm<<3];
int ans[maxm];
int res[maxn];
int lowbit(int x){
return (x & -x);
}
void update(int pos,int d){
while(pos < maxn){
res[pos] += d;
pos += lowbit(pos);
}
return;
}
int query(int pos){
int ret = 0;
while(pos){
ret += res[pos];
pos -= lowbit(pos);
}
return ret;
}
struct point{
int x,y;
int ans;
}p[maxm];
bool cmp(quest a,quest b){
return (a.x < b.x) || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.flag > b.flag);
}
int t;
int n,m,q;
int work(ll x){
int ret = 0;
while(x){
ret += x % 10;
x /= 10;
}
return ret;
}
int x,y,xx,yy;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
memset(res,0,sizeof(res));
cin >> n >> m >> q;
for(int i = 1;i <= m;++i){
cin >> p[i].x >> p[i].y;
ll pk = cal(p[i].x,p[i].y,n);
p[i].ans = work(pk);
e[4*q + i].x = p[i].x;
e[4*q + i].y = p[i].y;
e[4*q+i].id = q+i;
e[4*q+i].flag = 2;
}
int cnt = 4*q + m;
for(int i = 1;i <= q;++i){
cin >> x >> y >> xx >> yy;
e[4*(i-1) + 1].x = x-1;e[4*(i-1)+1].y = y-1;e[4*(i-1)+1].id = i;e[4*(i-1)+1].flag = 1;
e[4*(i-1) + 2].x = xx;e[4*(i-1)+2].y = yy;e[4*(i-1)+2].id = i;e[4*(i-1)+2].flag = 1;
e[4*(i-1) + 3].x = x-1;e[4*(i-1)+3].y = yy;e[4*(i-1)+3].id = i;e[4*(i-1)+3].flag = -1;
e[4*(i-1) + 4].x = xx;e[4*(i-1)+4].y = y-1;e[4*(i-1)+4].id = i;e[4*(i-1)+4].flag = -1;
}
sort(e+1,e+cnt+1,cmp);
for(int i = 1;i <= q;++i)
ans[i] = 0;
for(int i = 1;i <= cnt;++i){
if(e[i].flag == 2){
int now = e[i].id - q;
update(e[i].y,p[now].ans);
}
else{
ans[e[i].id] += e[i].flag * query(e[i].y);
}
}
for(int i = 1;i <= q;++i){
cout << ans[i] << "\n";
}
}
return 0;
}```

654 人读过

0 条评论