输入输出格式

输入格式:

 

第一履行1独数,表示序列的长短n

第二实施1单数,表示操作的次数w

后面依次是w行,分别代表参加与了解操作

其中,加入用x表示,询问用y表示

x的格式为”x a b” 表示以序列a的职位加上b

y的格式为”y a b” 表示询问a到b区间的加和

 

出口格式:

 

每行一个频繁,分别是每次询问的结果

 

输入输出格式

输入格式:

 

第1执: 两只用空格分开的整数M 和N

 

输出格式:

 

第1实行: 十单用空格分开的平头,分别代表数码(0..9)在班中出现的次数。

 

题目叙述

受一定一个尺寸为n(n<=100000),初始值都为0的行列,x(x<=10000)次的改动某些位置及之数字,每次添加一个数,然后提出y
(y<=10000)个问题,求诸段距离的及。时间范围1秒。

输入输出样例

输入样例#1:

129 137

输出样例#1:

1 10 2 9 1 1 1 1 0 1

 

 

 

翻开刷水题模式23333

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<map>
 6 #include<algorithm>
 7 #define LL long long int 
 8 using namespace std;
 9 const int MAXN=88000;
10 inline void read(int &n)
11 {
12     char c=getchar();n=0;bool flag=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 LL n,m;
17 LL ans[10];
18 int main()
19 {
20 //    read(n);read(m);
21     cin>>n>>m;
22     for(LL i=n;i<=m;i++)
23     {
24         LL p=i;
25         while(p)
26         {
27             ans[p%10]++,
28             p/=10;
29         }
30     }
31     for(int i=0;i<=9;i++)
32         printf("%lld ",ans[i]);
33     return 0;
34 }

 

 

输入输出样例

输入样例#1:

5
4
x 3 8
y 1 3
x 4 9
y 3 4

输出样例#1:

8
17

裸的线段树!

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #define ls k<<1
  8 #define rs k<<1|1
  9 using namespace std;
 10 const int MAXN=100001;
 11 void read(int &n)
 12 {
 13     char c='+';int x=0;bool flag=0;
 14     while(c<'0'||c>'9')
 15     {c=getchar();if(c=='-')flag=1;}
 16     while(c>='0'&&c<='9')
 17     {x=x*10+c-48,c=getchar();}
 18     flag==1?n=-x:n=x;
 19 }
 20 int n,m,chair;
 21 int ans=-1;
 22 int now=0;
 23 int you,mei;
 24 struct node
 25 {
 26     int l,r,w,fm;
 27 }tree[MAXN*4];
 28 void update(int k)
 29 {
 30     tree[k].w=tree[ls].w+tree[rs].w;
 31 }
 32 void pushdown(int k)
 33 {
 34     tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].fm;
 35     tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].fm;
 36     tree[ls].fm+=tree[k].fm;
 37     tree[rs].fm+=tree[k].fm;
 38     tree[k].fm=0;
 39     //cout<<"ls:"<<(ls)<<" "<<tree[ls].w<<" ";
 40     //cout<<"rs:"<<(rs)<<" "<<tree[rs].w<<" "<<endl;
 41 }
 42 void build_tree(int ll,int rr,int k)
 43 {
 44     tree[k].l=ll;tree[k].r=rr;
 45     if(ll==rr)
 46     {
 47         tree[k].w=0;
 48         return ;
 49     }
 50     int mid=(ll+rr)>>1;
 51     build_tree(ll,mid,ls);
 52     build_tree(mid+1,rr,rs);
 53     update(k);
 54 }
 55 void interval_ask(int ll,int rr,int k)
 56 {
 57     if(ll>tree[k].r||rr<tree[k].l)
 58         return ;
 59     if(ll<=tree[k].l&&tree[k].r<=rr)
 60     {
 61         ans+=tree[k].w;
 62         return ;
 63     }
 64     int mid=(tree[k].l+tree[k].r)>>1;
 65     if(tree[k].fm)
 66     pushdown(k);
 67     if(ll<=mid)
 68     interval_ask(ll,rr,ls);
 69     if(rr>mid)
 70     interval_ask(ll,rr,rs);
 71     if(tree[k].fm)
 72     pushdown(k);
 73 }
 74 void point_change(int pos,int v,int k)
 75 {
 76     if(pos>tree[k].r||pos<tree[k].l)
 77         return ;
 78     if(tree[k].l==tree[k].r)
 79     {
 80         tree[k].w+=v;
 81         return ;
 82     }
 83     point_change(pos,v,ls);
 84     point_change(pos,v,rs);
 85     update(k);
 86 }
 87 void interval_change(int ll,int rr,int num,int k)
 88 {
 89     if(ll>tree[k].r||rr<tree[k].l)
 90         return ;
 91     if(ll<=tree[k].l&&rr>=tree[k].r)
 92     {
 93         tree[k].w+=num;
 94         tree[k].fm+=(tree[k].r-tree[k].l+1)*num;
 95         return ;
 96     }
 97     int mid=(tree[k].l+tree[k].r)>>1;
 98     if(tree[k].fm)
 99     pushdown(k);
100     if(ll<=mid)
101     interval_change(ll,rr,num,ls);
102     if(rr>mid)
103     interval_change(ll,rr,num,rs);
104     update(k);
105 }
106 int main()
107 {
108     read(n);read(m);
109     build_tree(1,n,1);
110     for(int i=1;i<=m;i++)
111     {
112         char how;
113         cin>>how;
114         if(how=='x')
115         {
116             int pos,v;
117             read(pos);read(v);
118             point_change(pos,v,1);
119         }
120         else 
121         {
122             ans=0;
123             int x,y;
124             read(x);read(y);
125             interval_ask(x,y,1);
126             printf("%d\n",ans);
127         }
128     }
129     return 0;
130 } 

 

题材叙述

Bessie的大脑反应灵敏,仿佛真实地看了它再三了之一个又一个数。她起留心每一个数码(0..9):每一个数额以计数的长河中冒出过多少坏?

被闹些许个整数M 和N (1 ≤M ≤N ≤2,000,000,000 以及N-M
≤500,000),求诸一个数码出现了小坏。

譬如说考虑序列129–137: 129, 130, 131, 132, 133, 134, 135, 136,
137。统计后意识:

0出现了1次,1出现了10次,2出现了2次,3出现了9次,4出现了1次,5出现了1次,

6出现了1次,7出现了1次,8出现了0次,9出现了1次。

问题背景

Bessie 处于半梦半醒的状态。过了少时,她意识及她于勤频繁,不能够入眠。