比赛 |
EYOI暨SBOI暑假快乐赛3rd |
评测结果 |
AAAAAAAAAA |
题目名称 |
移动电话 |
最终得分 |
100 |
用户昵称 |
Restly |
运行时间 |
0.965 s |
代码语言 |
C++ |
内存使用 |
19.58 MiB |
提交时间 |
2022-06-27 11:34:03 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 30;
const int maxm = 3e5 + 5;
struct query {
int id,op,x,y,z,v;
query() {
id = op = x = y = z = v = 0;
}
query(int id,int op,int x,int y,int z,int v):id(id),op(op),x(x),y(y),z(z),v(v){}
}Q[maxm],s[maxm];
int c[maxn];
int cnt;
long long ans[maxm];
int n;
int lowbit(int x) {
return x & -x;
}
void add(int x,int y) {
if(x <= 0)return ;
for(;x <= n;x += lowbit(x))c[x] += y;
return ;
}
int Query(int x) {
if(x <= 0)return 0;
int ans = 0;
for(;x;x -= lowbit(x))ans += c[x];
return ans;
}
void solve(int l,int r) {
if(l >= r)return ;
int mid = l + r >> 1;
solve(l , mid);
solve(mid + 1 , r);
int i = l,j = mid + 1;
for(int k = l;k <= r;++ k) {
if(j > r||(i <= mid&&Q[i].x <= Q[j].x)) {
if(Q[i].op & 1)add(Q[i].y , Q[i].z);
s[k] = Q[i ++];
}
else {
if(Q[j].op == 2)ans[Q[j].id] += 1ll * Q[j].v * Query(Q[j].y);
s[k] = Q[j ++];
}
}
for(int k = l;k <= mid;++ k)add(Q[k].y , -Q[k].z);
for(int k = l;k <= r;++ k)Q[k] = s[k];
return ;
}
int main() {
freopen("mobilephones.in","r",stdin);
freopen("mobilephones.out","w",stdout);
int op;
cnt = 0;
int cur = 0;
while(~ scanf("%d",&op)) {
int x,y,z,l,r;
if(op == 3)break ;
if(op == 0)scanf("%d",&n);
else if(op == 1) {
scanf("%d%d%d",&x,&y,&z);
++ x;
++ y;
Q[++ cnt] = query(0 , op , x , y , z , 0);
}
else {
scanf("%d%d%d%d",&x,&y,&l,&r);
++ x;
++ y;
++ l;
++ r;
Q[++ cnt] = query(++ cur , op , l , r , 0 , 1);
Q[++ cnt] = query(cur , op , x - 1 , r , 0 , -1);
Q[++ cnt] = query(cur , op , l , y - 1 , 0 , -1);
Q[++ cnt] = query(cur , op , x - 1 , y - 1 , 0 , 1);
}
}
solve(1 , cnt);
for(int i = 1;i <= cur;++ i)printf("%lld\n",ans[i]);
return 0;
}