问题 D: Segment Balls
时间限制: 1 Sec 内存限制: 128 MB 提交: 253 解决: 37
题目描述
Small K has recently earn money in stock market , so he want to make balls to celebrate it.
Now he buys so many balls , and he want to put it into the boxes , he will have two operators to do it.
There are n boxes , which number is in range of (1 , n)
operator 1: PUT B C he can put C balls to boxes whose number is multiple of B
operator 2: QUERY D E he want to know the total number of balls in boxes number D to boxes number E.
We guarantee that 1 <= B ,C <= 10 1 <= D <= E <= 1e6
输入
The first number CASE is the case number.Then will be CASE cases.
At every case , the first number is n(1<=n<=10^6) ,means that we have n boxes.
the second number is q , which means the q operators will be give.
And then will be q lines ,which means q operators.
(1 <= q <= 100000)
输出
Every case , print the total balls for every question . A question a line.
样例输入
1
4
8
PUT 1 3
QUERY 2 4
PUT 2 3
QUERY 1 4
QEURY 1 1
QEURY 2 2
QUERY 3 3
QUERY 4 4
样例输出
9
18
3
6
3
6 题意:有n个空盒子,进行两种操作:
1)PUT x y 给标号为x的倍数的盒子全加上y个球。
2)QUERY x y 求标号从x到y的盒子里总球数。
分析:维护每次给线段加的倍数x及加数y,那么给每段加上y*(该段上x的倍数点总数(r-l)/x)即可维护每段的总和,x最多有
10种,因此刚开始直接来用第二维为10的lazy数组标志,但爆内存了,后来改用vector,代码各种乱,还好最后几分钟AC了。
这题有更简便的方法,直接开个大小为11的数组记录好整段每种的倍数的put值,最后加上所有的put值乘以线段长度/倍数x即可。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 1000010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int n;
struct node
{
int x,y;
};
LL sum[N<<];
vector<node>col[N<<];
void Pushup(int rt)
{
int ls=rt<<,rs=ls|;
sum[rt]=sum[ls]+sum[rs];
}
void build(int l,int r,int rt)
{
if(l==r)
{
sum[rt]=;
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
Pushup(rt);
}
int cal(int i,int l,int r)//计算该段倍数为i的点总数
{
int len=,num=;
for(int j=l;j<=r&&num<=;j++)
{
num++;
if(j%i==)
{
l=j;len++;
break;
}
}
len+=(r-l)/i;
return len;
}
void Pushdown(int rt,int l,int r)
{
int ls=rt<<,rs=ls|;
int m=(l+r)>>;
for(int i=,sz=col[rt].size();i<sz;i++)
if(col[rt][i].y)
{
int flag=;
for(int j=,z=col[ls].size();j<z;j++)//维护10种x值即可
{
if(col[ls][j].x==col[rt][i].x)
{
col[ls][j].y+=col[rt][i].y;flag=;break;
}
}
if(!flag)col[ls].push_back(col[rt][i]);
flag=;
for(int j=,z=col[rs].size();j<z;j++)
{
if(col[rs][j].x==col[rt][i].x)
{
col[rs][j].y+=col[rt][i].y;flag=;break;
}
}
if(!flag)col[rs].push_back(col[rt][i]);
sum[ls]+=1LL*col[rt][i].y*cal(col[rt][i].x,l,m);//同样维护好sum值
sum[rs]+=1LL*col[rt][i].y*cal(col[rt][i].x,m+,r);
}
col[rt].clear();
}
void update(int L,int R,int x,int y,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
int flag=;
for(int i=,sz=col[rt].size();i<sz;i++)//维护10种x值即可
{
if(col[rt][i].x==x)
{
col[rt][i].y+=y;flag=;break;
}
}
node now;
now.x=x;now.y=y;
if(!flag)col[rt].push_back(now);
sum[rt]+=1LL*y*cal(x,l,r);//加上y*(x的倍数点和)
return;
}
}
LL query(int L,int R,int l,int r,int rt)//求区间和
{
if(L<=l&&r<=R)return sum[rt];
Pushdown(rt,l,r);
int m=(l+r)>>;
LL res=;
if(L<=m)res+=query(L,R,lson);
if(m<R)res+=query(L,R,rson);
return res;
}
int main()
{
int T,q;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)col[i].clear();
build(,n,);
while(q--)
{
char op[];
int x,y;
scanf("%s%d%d",op,&x,&y);
if(op[]=='P')
{
update(,n,x,y,,n,);
}
else
{
if(x>n)
{
puts("");continue;
}
if(y>n)y=n;
printf("%lld\n",query(x,y,,n,));
}
}
}
}