我人傻了,样例过了,数据点全WA
  • 板块P2068 统计和
  • 楼主youyi2008
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/7/7 12:18
  • 上次更新2023/10/27 21:37:57
查看原帖
我人傻了,样例过了,数据点全WA
334935
youyi2008楼主2022/7/7 12:18
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#pragma GCC optimize(2)
//#pragma GCC optimize(3)
#endif
#define INF 0x3f3f3f3f
#define N 500005
#define ll long long
#define ull unsigned long long
#define il inline
#define rg register
using namespace std;
ull n, m;
ull tr[N];

// lowbit求x的二进制码最低位的1
ull lowbit(ull x)
{
    //计算机中,正整型的储存码就是其二进制码
    //负数的二进制码为其相反数二进制码的反码+1
    //两个码按位与可得到该数二进制码最低位的1
    return x & -x;
}

//单点加操作
void add(ull x, ull c)
{
    //将数组中第x位本身及其父节点全部更新,加上c
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}

//求a[1...x]区间和操作
ull sum(ull x)
{
    ull res = 0;
    //将属于本区间的数全部相加
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
int main()
{
    // cin.sync_with_stdio(false);
    // freopen("P2068_1.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'x')
            add(x, y);
        //求a[x...y]的区间和
        //即为a[1...y]的区间和减去a[1...x-1]的区间和
        if (c == 'y')
            cout << sum(y) - sum(x - 1) << endl;
    }
    system("pause");
    return 0;
}
2022/7/7 12:18
加载中...