记录编号	589034	评测结果	AAAAAAAAAA
题目名称	Vera 与现代艺术	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	9.616 s
提交时间	2024-07-02 17:02:19	内存使用	65.02 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 2e5 + 5;
int n = mread(), m = mread(), r[N], c[N], s[N * 6], ans[N];
vector<array<int, 5> > v;
vector<array<int, 3> > q;
vector<array<int, 4> > ch;
map<int, int> ap;
void add(int x, int k){
    while(x <= n * 6){
        s[x] += k;
        x += x & -x;
    }
    return;
}
int query(int x){
    int ans = 0;
    while(x){
        ans += s[x];
        x -= x & -x;
    }
    return ans;
}
signed main(){
    for(int i = 1; i <= n; i ++){
        int x = mread(), y = mread(), v2 = mread();
        int t1 = 0, t2 = 0;
        for(int i = 0; i <= 60; i ++){
            t1 <<= 1ll;
            t1 += x & 1ll;
            x >>= 1ll;
        }
        for(int i = 0; i <= 60; i ++){
            t2 <<= 1ll;
            t2 += y & 1ll;
            y >>= 1ll;
        }
        int a = t1 & -t1, b = t2 & -t2;
        v.push_back({t1 - a + 1, t1 - 1 + a, t2 - b + 1, t2 - 1 + b, v2});
        ap[t1 - a + 1] = 1, ap[t1 - 1 + a] = 1, ap[t2 - b + 1] = 1, ap[t2 - 1 + b] = 1;
        // printf("### %lld %lld %lld %lld\n", t1 - a + 1, t1 - 1 + a, t2 - b + 1, t2 - 1 + b);
    }
    for(int i = 1; i <= m; i ++){
        r[i] = mread(), c[i] = mread();
        // cout << (bitset<62>)r[i] << " " << (bitset<62>)c[i] << " ";
        int t1 = 0, t2 = 0;
        for(int j = 0; j <= 60; j ++){
            t1 <<= 1ll;
            t1 += r[i] & 1ll;
            r[i] >>= 1ll;
        }
        for(int j = 0; j <= 60; j ++){
            t2 <<= 1ll;
            t2 += c[i] & 1ll;
            c[i] >>= 1ll;
        }
        r[i] = t1, c[i] = t2;
        // cout << t1 << " " << t2 << "\n";
        ap[t1] = 1, ap[t2] = 1;
    }
    int now = 0;
    {
        for(auto &t : ap){
            t.se = ++now;
        }
    }
    for(auto &t : v){
        t[0] = ap[t[0]], t[1] = ap[t[1]], t[2] = ap[t[2]], t[3] = ap[t[3]];
        ch.push_back({t[0], t[2], t[3], t[4]});
        ch.push_back({t[1], t[2], t[3], -t[4]});
    }
    for(int i = 1; i <= m; i ++){
        r[i] = ap[r[i]], c[i] = ap[c[i]];
        q.push_back({r[i], c[i], i});
    }
    // printf("***\n");
    sort(q.begin(), q.end());
    sort(ch.begin(), ch.end());
    int it1 = 0, it2 = 0;
    for(int i = 1; i <= now; i ++){
        while(it1 < ch.size() && ch[it1][0] == i){
            add(ch[it1][1], ch[it1][3]);
            add(ch[it1][2] + 1, -ch[it1][3]);
            // printf("*** %lld %lld %lld %lld\n", ch[it1][0], ch[it1][1], ch[it1][2], ch[it1][3]);
            it1 ++;
        }
        while(it2 < q.size() && q[it2][0] == i){
            ans[q[it2][2]] = query(q[it2][1]);
            // printf("--- %lld %lld %lld\n", q[it2][0], q[it2][1], q[it2][2]);
            it2 ++;
        }
    }
    for(int i = 1; i <= m; i ++)
    printf("%lld\n", ans[i]);
    return 0;
}