HDU 4267 A Simple Problem with Integers(12年长春市线段树)

HDU 4267 A Simple Problem with Integers(12年长春线段树)

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：给出n个数，每次将一段区间内满足(i-l)%k==0 （r>=i>=l）的数ai增加c

http://acm.hdu.edu.cn/showproblem.php?pid=4267

比较容易往线段树上想的。但是由于更新的是一些离散的点，比较麻烦

可以考虑这些点的共性，总是隔几个，更新一个，那窝萌把区间内的数关于k的余数分组

这样每次更新的都是其中的一组，而且是连续的。

由于 K比较小，这是本题的突破口，那么关于k的余数情况，最多只有55种。

即如果k=1，则分为1组，k=2分为2组……

一开始傻叉了打算维护55棵线段树，其实也是可以的，更新只需要1棵，查询是10棵，还是可以接受的。

不过只需要在线段树结点维护这55种情况即可。

不过内存比较紧，要把所有的情况压缩一下，不能开10*10的空间。

同样更新只需要一个，最终统计的话，需要遍历所有的K，也就是最多是10.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<vector>
#include<string>
#include<map>
#define eps 1e-7
#define LL long long
#define N 500005
#define zero(a) fabs(a)<eps
#define lson step<<1
#define rson step<<1|1
#define MOD 1234567891
#define pb(a) push_back(a)
using namespace std;
struct Node{
    int left,right,add[55],sum;
    int mid(){return (left+right)/2;}
}L[4*N];
int a[N],n,b[11][11];
void Bulid(int step ,int l,int r){
    L[step].left=l;
    L[step].right=r;
    L[step].sum=0;
    memset(L[step].add,0,sizeof(L[step].add));
    if(l==r) return ;
    Bulid(lson,l,L[step].mid());
    Bulid(rson,L[step].mid()+1,r);
}
void push_down(int step){
    if(L[step].sum){
        L[lson].sum+=L[step].sum;
        L[rson].sum+=L[step].sum;
        L[step].sum=0;
        for(int i=0;i<55;i++){
                L[lson].add[i]+=L[step].add[i];
                L[rson].add[i]+=L[step].add[i];
                L[step].add[i]=0;
        }
    }
}
void update(int step,int l,int r,int num,int i,int j){
    if(L[step].left==l&&L[step].right==r){
        L[step].sum+=num;
        L[step].add[b[i][j]]+=num;
        return;
    }
    push_down(step);
    if(r<=L[step].mid()) update(lson,l,r,num,i,j);
    else if(l>L[step].mid()) update(rson,l,r,num,i,j);
    else {
        update(lson,l,L[step].mid(),num,i,j);
        update(rson,L[step].mid()+1,r,num,i,j);
    }
}
int query(int step,int pos){
    if(L[step].left==L[step].right){
        int tmp=0;
        for(int i=1;i<=10;i++)  tmp+=L[step].add[b[i][pos%i]];
        return a[L[step].left]+tmp;
    }
    push_down(step);
    if(pos<=L[step].mid()) return query(lson,pos);
    else return query(rson,pos);
}
int main(){
    int cnt=0;
    for(int i=1;i<=10;i++) for(int j=0;j<i;j++) b[i][j]=cnt++;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        Bulid(1,1,n);
        int q,d;
        scanf("%d",&q);
        while(q--){
            int k,l,r,m;
            scanf("%d",&k);
            if(k==2){
                scanf("%d",&m);
                printf("%d\n",query(1,m));
            }
            else{
                scanf("%d%d%d%d",&l,&r,&d,&m);
                update(1,l,r,m,d,l%d);
            }
        }
    }
    return 0;
}

4楼zzp441524586昨天 23:06: 跪love神。。。求当时是怎么想到按K来分组的？~~蒻菜被这道题虐了一下午T^T。。。

3楼tclh123昨天 23:03: 55。。。10*10 MLE的弱逼路过。。。30000+K的内存也太飘逸了

2楼zero0914昨天 22:24: 我11*11*200100没有MLE啊，一把就过了

1楼go_zyw昨天 20:31: 看来只有我是离线刷k次的。。

HDU 4267 A Simple Problem with Integers(12年长春市 线段树)

相关推荐

HDU 4267 A Simple Problem with Integers(12年长春市线段树)