洛谷 U86564 排队形洛谷 U86564 排队形

题目背景

(JDFZ2019)秋季运动会开始辣！为了使强大的高一 · (6)班有一个更好的精神面貌，班主任(T)老师和体委(LY)，(LYB)开始排班级的队形......

题目描述

队形是一个不规则图形（要是规则的话还排什么），分为(N)列，每列有数量不定的同学（排队开始前每列都没有同学）。三个排队形的人有明确的分工：(LY)（代号为(A)）负责往队列中加人，(LYB)（代号为(B)）负责从队列中减去使队列不协调的人，而(T)老师（代号为(C)）只需要检查就可以了。排队开始后，他们会按时间顺序发出不同的指令（为了与其他人区别开，他们每个人发出指令前都会喊出自己的代号）：(LY)发出的指令中包括两个数(M_1,K_1)，表示第(M_1)列加入(K_1)位同学；(LYB)发出的指令中包括两个数(M_2,K_2)，表示第(M_2)列中删除(K_2)位同学；(T)老师发出的指令中也包括两个数(P,Q)，表示她现在想知道从第(P)列到第(Q)列的总人数。

输入格式

第一行有两个整数(N,D)，表示有(N)列，(D)个指令。

接下来有(D)行，每行开头先包括一个代号（(A,B,C)其中的一个），并按题目所述发出他/她的指令。

输出格式

输出行数与(T)老师的提问数相等，每行一个整数，回答(T)老师的问题。

样例输入

样例输出

提示：

数据范围：

对于30%的数据，(1le N,Dle 10^4)，(T)老师至少提问(1000)次。

对于全部数据，(1le N,Dle 10^5)，(T)老师至少提问(30000)次。

题解：

树状数组的题目。

我觉得应该算是裸题了，最后区间统计利用前缀和的思想就好。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,d;
int tree[500001];
void update(int x,int y)
{
    for(int i=x;i<=n;i+=i&-i)
        tree[i]+=y;
}
int query(int x)
{
    int ret=0;
    for(int i=x;i;i-=i&-i)
        ret+=tree[i];
    return ret;
}
int main()
{
    //freopen("6.in","r",stdin);
    //freopen("6.out","w",stdout);
    scanf("%d%d",&n,&d);
    while(d--)
    {
        char ch;
        cin>>ch;
        if(ch=='A')
        {
            int m,k;
            scanf("%d%d",&m,&k);
            update(m,k);
        }
        else if(ch=='B')
        {
            int m,k;
            scanf("%d%d",&m,&k);
            update(m,-k);
        }
        else if(ch=='C')
        {
            int p,q;
            scanf("%d%d",&p,&q);
            printf("%d
",query(q)-query(p-1));
        }
    }
    return 0;
}

洛谷 U86564 排队形 洛谷 U86564 排队形