UVa 12086 : Potentiometers

問題リンク : http://uva.onlinejudge.org/external/120/12086.pdf

問題概要 :
長さNの数列とクエリーが与えられる
クエリーの種類と効果は次の通り
1. S x y
数列のx番目の要素 ( 1-indexed ) を y に変更する

2. M x y
数列のx番目の要素からy番目の要素までの値の総和を出力

制約 :
N は最大 2 * 10^5
クエリーは最大 2 * 10^5

解法：
BIT、RMQ、平方分割などなど
ここでは平方分割で解いたものを残す
sqrt(N)で分割するので、
初期化はO(N)
クエリーSはO(1)
クエリーMはO(sqrt(N))
sqrt(N) は最大でも４５０くらい

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

int N,x,y,sqr;
vector<ll> vec,bucket;
char opr[10];

void init(){

  bucket.clear();
  sqr = floor(sqrt((double)N));
  int i = 0,cnt = 0;
  ll sum = 0;
  while( i < N ) {
    sum += vec[i];
    ++cnt, ++i;
    if( cnt == sqr ) {
      cnt = 0;
      bucket.push_back(sum);
      sum = 0;
    }
  }
  if( cnt ) bucket.push_back(sum);

}

void update(int cur,ll value){
  int bcur = floor((double)cur/(double)sqr);
  bucket[bcur] -= vec[cur];
  bucket[bcur] += value;
  vec[cur] = value;
}

ll query(int L,int R){ // [L,R]


  int left  = floor((double)L/(double)sqr);
  int right = floor((double)R/(double)sqr);

  ll ret = 0;
  if( left == right ) {
    REP(i,L,R+1) ret += vec[i];
  } else {
    int p = ( left + 1 ) * sqr;
    REP(i,L,p) ret += vec[i];
    p = right * sqr;
    REP(i,p,R+1) ret += vec[i];
    REP(i,left+1,right) ret += bucket[i];
  }
  return ret;
}

int main(){
  vec.clear();
  vec.resize(300000,0);
  int CNT = 1;
  while( scanf("%d",&N), N ){

    rep(i,N) scanf("%lld",&vec[i]);

    if( CNT != 1 ) puts("");
    printf("Case %d:\n",CNT++);

    init();

    while( 1 ){
      scanf("%s",&opr[0]);
      if( string(opr) == "END" ) break;
      scanf("%d %d",&x,&y);

      if( opr[0] == 'S' ) {
        --x;
        update(x,(ll)y);
      } else {
        --x, --y;
        printf("%lld\n",query(x,y));
      }
    }

  }
  return 0;
}