首页 > 代码库 > Vijos 1320 清点人数

Vijos 1320 清点人数

2024-09-20 04:51:46   216人阅读

背景

NK中学组织同学们去五云山寨参加社会实践活动，按惯例要乘坐火车去。由于NK中学的学生很多，在火车开之前必须清点好人数。

描述

初始时，火车上没有学生；当同学们开始上火车时，年级主任从第一节车厢出发走到最后一节车厢，每节车厢随时都有可能有同学上下。年级主任走到第m节车厢时，他想知道第１到m这m节车厢上一共有多少学生，但是他没有调头往回走的习惯．也就是说每次当他提问时，m总会比前一次大。

格式

输入格式

第一行两个整数n,k，表示火车共有n节车厢以及k个事件。接下来有k行，按时间先后给出k个事件，每行开头都有一个字母A,B或C，如果字母为A，接下来是一个数m，表示年级主任现在在第m节车厢；如果为B，接下来两个数m,p，表示在第m节车厢有p名学生上车；如果为C，接下来两个数m,p，表示在第m节车厢有p名学生下车。学生总人数不会超过100000。

输出格式

有多少个A就输出多少行，每行一个整数，回答年级主任提出的问题。

样例1

样例输入1

10 7A 1B 1 1B 3 1B 4 1A 2A 3A 10
Copy

样例输出1

0123
Copy

限制

各个测试点1s

提示

注意:对于30%的数据,n<=10000,k<=10000 至少有3000个A
对于100%的数据n<=500000,k<=100000. 至少有30000个A

来源

命题:cauchy

审题:彩虹阴影
数据:彩虹阴影

 

随机求前缀和，暴力可以全T

所以用线段树区间修改，每次修改1-m

查询就普通的查询就好了

 

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;struct TreeNodeType{    int l,r,dis,flag;};struct TreeNodeType tree[500000*4+15];int n,m,a,b,x,s;char if_;void tree_up(int now){    tree[now].dis=tree[now<<1].dis+tree[now<<1|1].dis;    }//void tree_down(int now)//{//    tree[now*2].flag+=tree[now].flag;//    tree[now*2+1].flag+=tree[now].flag;//    tree[now*2].dis+=tree[now].flag*(tree[now*2].r-tree[now*2].l+1);//    tree[now*2+1].dis+=tree[now].flag*(tree[now*2+1].r-tree[now*2+1].l+1);//    tree[now].flag=0;//    //}void tree_build(int now,int l,int r){    tree[now].l=l;tree[now].r=r;    if(tree[now].l==tree[now].r)//    {//        cin>>tree[now].dis;        return ;//    }    int mid=(tree[now].l+tree[now].r)/2;    tree_build(now*2,l,mid);    tree_build(now*2+1,mid+1,r);    tree_up(now);}void tree_change(int k,int l,int r,int x){    if(tree[k].l==l&&tree[k].r==r)    {        tree[k].dis+=x*(tree[k].r-tree[k].l+1);        tree[k].flag+=x;        return ;    }//    if(tree[k].flag) tree_down(k);    int mid=(tree[k].l+tree[k].r)/2;    if(l>mid) tree_change(k*2+1,l,r,x);    else if(r<=mid) tree_change(k*2,l,r,x);    else {        tree_change(k*2,l,mid,x);        tree_change(k*2+1,mid+1,r,x);    }    tree_up(k);}int tree_find(int k,int l,int r){//    if(tree[k].l==tree[k].r) return tree[k].dis;//    if(tree[k].flag) tree_down(k);//    int mid=(tree[k].r+tree[k].l)/2;//    if(to>mid) return tree_find(k*2+1,to);//    else return tree_find(k*2,to);    if(tree[k].l==l&&tree[k].r==r) return tree[k].dis;    int mid=tree[k].l+tree[k].r>>1;    if(l>mid) return tree_find(k<<1|1,l,r);    else if(r<=mid) return tree_find(k<<1,l,r);    else return tree_find(k<<1,l,mid)+tree_find(k<<1|1,mid+1,r);}int main(){    cin>>n>>m;    tree_build(1,1,n);    for(int i=1;i<=m;i++)    {        cin>>if_;        if(if_==‘A‘)        {            cin>>s;            int sb=tree_find(1,1,s);            cout<<sb<<endl;        }        else if(if_==‘B‘)        {            cin>>b>>x;            tree_change(1,b,b,x);        }        else if(if_==‘C‘)        {            cin>>b>>x;            tree_change(1,b,b,-x);        }     }     return 0; }

 

Vijos 1320 清点人数


联系
我们