HDU-4627(セグメントツリー)

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxn = 50110;

int  MIN[11][maxn<<2];
int col[11][maxn<<2];
int id[11][maxn],vis[11][maxn];

void build(int l,int r,int rt){
for(int i=1;i<=10;i++) MIN[i][rt]=0;
for(int i=1;i<=10;i++) col[i][rt]=0;
if(l==r) return ;
int m=(l+r)>>1;
build(lson);
build(rson);
}

void pushup(int l,int r,int rt,int i){
MIN[i][rt]=min(MIN[i][rt<<1],MIN[i][rt<<1|1]);
}

void pushdown(int l,int r,int rt,int i){
if(l==r){
    col[i][rt]=0;
    return ;
}
if(col[i][rt]){
    col[i][rt<<1]+=col[i][rt];
    MIN[i][rt<<1]+=col[i][rt];
    col[i][rt<<1|1]+=col[i][rt];
    MIN[i][rt<<1|1]+=col[i][rt];
    col[i][rt]=0;
}
}

int ql,qr,addv;
void update(int l,int r,int rt,int i){
if(ql<=l&&r<=qr){
      col[i][rt]+=addv;
      MIN[i][rt]+=addv;
     // cout<<l<<"-->"<<r<<" "<<(r-l+1)*addv<<endl;
      return ;
}
pushdown(l,r,rt,i);
int m=(l+r)>>1;
if(ql<=m) update(lson,i);
if(qr> m) update(rson,i);
pushup(l,r,rt,i);
}

int res;
int posi;
void query(int l,int r,int rt,int i){
if(l==r){
    res+=MIN[i][rt];
         // cout<<l<<"-->"<<r<<" "<<sum[i][rt]<<endl;
    return ;
}
pushdown(l,r,rt,i);
int m=(l+r)>>1;
if(posi<=m) query(lson,i);
else if(posi> m) query(rson,i);
}

int lim = 50010;

int find(int yu,int wei,int i){
int x=0,y=lim;
while(x<y){
    int m = x + (y - x)/2;
    if(id[i][m]%i>yu) y=m;
    else if(id[i][m]%i<yu) x=m+1;
    else {
        if(id[i][m]/i==wei) return m;
        if(id[i][m]/i >wei) y=m;
        else x = m+1;
    }
  // cout<<m<<" "<<id[i][m]<<" "<<id[i][m]%i<<endl;
}
}
int query_id(int st,int ed,int k,int i){
int x = st % k;
int l = 0,r=lim;
while(l<r){    //  
    int m = l + ( r- l)/2;
    if(x + m*k>=st) r=m;
    else l=m+1;
}

int si = l;    // cout<<"start-->"<<si<<endl;




l = 0,r=lim;
while(l<r){    //  
    int m = l + ( r- l)/2;
    if(x + m*k<=ed) l=m+1;
    else r=m;
}
int ei = l-1;  //  cout<<"end-->"<<ei<<endl;
ql = find(x,si,i);
qr = find(x,ei,i);
}
int main()
{
    for(int i=1;i<=10;i++){
        int te=0;
        for(int j=0;j<i;j++){
            for(int k=j;k<lim;k+=i){
              id[i][te++]=k;
        }
    }

   int n;
    while(scanf("%d",&n)==1){
        for(int i=0;i<n;i++){
            scanf("%d",&id[0][i]);
        }

        build(0,lim,1);
        int Q;
        scanf("%d",&Q);
        while(Q--){
            int cmd;
            scanf("%d",&cmd);
            if(cmd==1){
                int a,b,k;
                scanf("%d %d %d %d",&a,&b,&k,&addv);
                query_id(a,b,k,k);
                update(0,lim,1,k);
            }
            else {
                int pos;
                scanf("%d",&pos);
                res=0;
                res+=id[0][pos-1];
                for(int i=1;i<=10;i++){
                    int yu= pos%i,wei=pos/i;
                    posi=find(yu,wei,i);
                    query(0,lim,1,i);
                }
                printf("%d
",res);
            }
        }
    }
    return 0;
}