弹药分配 (HGOI 2019.2.17 T2)

2019-02-17 15:16:20


题目大意

给出一个数列$a_1…a_n$,有两个操作:1.给出一个区间[a,b],给这个区间内所有编号(i-a)%k=0的数加上c; 2.询问编号为x的值

数据范围

n,m<=50000,1<=k<=10,ans<=maxlongint

解法

显然,直接暴力极限数据是会T的,但是这次好像数据很水,被一部分人水过去了

这道题,显然有间隔地只能一个一个修改,我们不能用线段树或者树状数组来处理。但是如果把它们放到一起就能处理了

用一个三维数组p[i][j][k]存间隔为i,除i余数为j,的第k个被加了多少。然后操作的时候集中用树状数组区间加

在询问的时候,树状数组单点询问,但记得要把所有的间隔枚举一遍都加起来

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) x&(-x)
using namespace std;
int n,m;
int a[50100];
int p[20][20][50100];
void Add(int b,int c,int x,int y)
{
    while(x<=n)
    {
        p[b][c][x]+=y;
        x+=lowbit(x);
    }
}
int sum(int b,int c,int x)
{
    int res=0;
    while(x>0)
    {
        res+=p[b][c][x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    while(m--)
    {
        int tmp,x,y,k,c;
        scanf("%d",&tmp);
        if(tmp==1)
        {
            scanf("%d%d%d%d",&x,&y,&k,&c);
            Add(k,x%k,x/k+1,c);
            Add(k,x%k,(y-x%k)/k+2,-c);//树状数组用差分实现区间加
        }
        else
        {
            scanf("%d",&x);
            int res=0;
            for(int i=1;i<=10;i++)
                res+=sum(i,x%i,x/i+1);//所有间隔枚举相加
            printf("%d\n",a[x]+res);
        }
    }
    return 0;
}