RUQ(Range Update Query)問題c++で解いてみた[備忘録] - プログラミング上達したい人が書くブログ

問題URL

Range Update Query (RUQ) | Aizu Online Judge

RUQとは

　AOJの問題文から引用させてもらうと、

数列 A = {a₀,a₁ ,...,a_n−1} に対し、次の２つの操作を行うプログラムを作成せよ。

update(s,t,x): a_s,a_s+1,...,a_t をxに変更する。
find(i): a_i の値を出力する。

ただし、a_i (i=0,1,...,n−1)は、2³¹-1で初期化されているものとする。

といった文言が書かれています。この問題では、nの範囲が100000まであり、updateとfindも合わせて最大100000回実行できるプログラムを作らなければなりません。

　これをなにも考えずに作ると、時間制限である1秒を超えてしまいます。実際、私も一度作りましたが、あるテストケースで1.73秒掛かってしまいました。そこで、出てくるのがRUQと呼ばれるデータ構造を使うことです。

kujira16.hateblo.jp

　上記のURLにあるブログの説明がRUQの図解付きで、非常にわかりやすかったです。

RUQを使って通したソースコード

・REP(i,n)で、for(int i = 0;i < n;i++)を省略しています。

・fill(from,to,num)で配列を同じ数字で埋めることが可能です。

・fill_n(from, num1, num2)で、fromからnum1個の数をnum2で埋めることができます。

・上記URLのRUQの説明を読んでください。

　下記ソースコードの配列aは、上記問題文にもある数列のことです。配列lazyは、数列aを√n個ずつの数列に分割したときに使われるものです。

　ところどころ現れる、

if(lazy[t/sq] >= 0){ fill_n(a+(t/sq)*sq,sq,lazy[t/sq]); lazy[t/sq] = -1; }

といったコードは、lazyに入っている数字をaに伝播させています。

　REP(i,q)内の2番目のif文であるif(t/sq == s/sq)という部分は、a[s]とa[t]が同じlazyのグループに存在しているかを判定しています。そして、そのif文内部でも、sからtがグループの端から端まで包括しているかしてないかでも場合分けしています。

　REP(i,q)内の２番目のif文に対応したelse文内では、まず、1つグループすべての値を変更しない部分、つまり端の部分のaを直接変えています。次に、グループ内すべてを変えるものに対応したlazyを変えています。

　つまり、例えばnが11になると、0,1,2,3,4,5,6,7,8,9,10という配列の添え字をもつ物ができます。そして、これは、|0,1,2|3,4,5|6,7,8|9,10|という部分に分けられます。このとき、update(1,9,num)を実行すると、3から8はグループ内すべてを変更するためlazyを変えています。しかし、1と2、9はグループ内すべてを変えるわけではないためaを直接変えています。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  int n,q;
  cin >> n >> q;
  vector  res;
  int a[n];
  int sq = sqrt(n);
  int nsq = n/sq+1;
  int lazy[nsq];
  fill(a,a+n,2147483647);//初期化
  fill(lazy,lazy+nsq,-1);//初期化
  REP(i,q){
    int z;
    cin >> z;
    if(z == 0){
      int s,t,x;
      cin >> s >> t >> x;

      
      if(t/sq == s/sq){//同じグループに属していた時
	if(lazy[t/sq] >= 0){//lazyが0以上ということは値が入っている
          //aの値を変更する前には必ず伝播させる
          //伝播させたらlazyで使った部分を初期化しておく
	  fill_n(a+(t/sq)*sq,sq,lazy[t/sq]);
	  lazy[t/sq] = -1;
	}
	if(t-s+1 == sq){
	  lazy[t/sq] = x;
	}
	else{
	  fill_n(a+s,t-s+1,x);
	}
      }

      else{
	int f = s,to = t;
	while(to%sq != (sq - 1)){
	  to--;
	}
	while(f%sq != 0){
	  f++;
	}
	if(lazy[t/sq] >= 0){
          //aの値を変える前の伝播
	  fill_n(a+(t/sq)*sq,sq,lazy[t/sq]);
	}
	if(lazy[s/sq] >= 0){
	  fill_n(a+(s/sq)*sq,sq,lazy[s/sq]);
	}
	fill_n(a+to+1,t-to,x);
	lazy[t/sq] = -1;
	fill_n(a+s,f-s,x);
	lazy[s/sq] = -1;
	f = f/sq;
	to = to/sq;
	if(f <= to){
	  fill_n(lazy+f,to-f+1,x);
	}
	
      }
      
    }
    else{
      int x;
      cin >> x;
      int te = x / sq;
      
      if(lazy[te] < 0){
	//cout << a[x] << endl;
	res.pb(a[x]);
      }
      else{
	fill_n(a+te*sq,sq,lazy[te]);//伝播
	lazy[te] = -1;
	//cout << a[x] << endl;
	res.pb(a[x]);

      }
      
    }
    
  }
  for(int i = 0;i < res.size();i++){
    cout << res[i] << endl;
  }
  return 0;
}