比赛 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;
}