首页 > 代码库 > AOJ DSL_2_D Range Update Query (RUQ)

AOJ DSL_2_D Range Update Query (RUQ)

2024-08-27 16:32:17   216人阅读

Range Update Query

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

  • update(s,t,x): as,as+1,...,at をxに変更する。
  • find(i): ai の値を出力する。

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

入力

n qquery1query2:queryq

１行目にAの要素数n, クエリの数qが与えられる。続くq行にi 番目のクエリ queryi が与えられる。queryi は以下のいずれかの形式で与えられる。

0 s t x

または

1 i

各クエリの最初の数字は、クエリの種類を示し、‘0‘がupdate(s,t,x)、‘1‘がfind(i) を表す。

出力

各findクエリについて、値を１行に出力せよ。

制約

  • 1≤n≤100000
  • 1≤q≤100000
  • 0≤s≤t<n
  • 0≤i<n
  • 0≤x<231−1

入力例 1

3 50 0 1 10 1 2 30 2 2 21 01 1

出力例 1

13

入力例 2

1 31 00 0 0 51 0

出力例 2

21474836475
 
 

区间修改，单点查询，线段树+tag标记。压了压常数，继续打榜。

 

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4  5 #define siz 10000000 6  7 char buf[siz], *bit = buf; 8  9 inline int nextInt(void) {10     register int ret = 0;11     register int neg = false;12 13     for (; *bit < ‘0‘; ++bit)14         if (*bit == ‘-‘)neg ^= true;15 16     for (; *bit >= ‘0‘; ++bit)17         ret = ret * 10 + *bit - ‘0‘;18 19     return neg ? -ret : ret;20 }21 22 #define inf 214748364723 24 int n, m;25 26 int tag[400005];27 28 int find(int t, int l, int r, int p) {29     if (~tag[t])30         return tag[t];31     int mid = (l + r) >> 1;32     if (p <= mid)33         return find(t << 1, l, mid, p);34     else35         return find(t << 1 | 1, mid + 1, r, p);36 }37 38 void update(int t, int l, int r, int x, int y, int k) {39     if (l == x && r == y)40         tag[t] = k;41     else {42         int mid = (l + r) >> 1;43         if (~tag[t])44             tag[t << 1] = tag[t << 1 | 1] = tag[t], tag[t] = -1;45         if (y <= mid)46             update(t << 1, l, mid, x, y, k);47         else if (x > mid)48             update(t << 1 | 1, mid + 1, r, x, y, k);49         else {50             update(t << 1, l, mid, x, mid, k);51             update(t << 1 | 1, mid + 1, r, mid + 1, y, k);52         }53     }54 }55 56 signed main(void) {57     fread(buf, 1, siz, stdin);58 59     n = nextInt();60     m = nextInt();61 62     for (int i = 0; i < (n << 2); ++i)63         tag[i] = inf;64 65     for (int i = 1; i <= m; ++i) {66         int c = nextInt();67         if (c)    // find(x)68             printf("%d\n", find(1, 1, n, nextInt() + 1));69         else {70             int x = nextInt();71             int y = nextInt();72             int k = nextInt();73             update(1, 1, n, x + 1, y + 1, k);74         }75     }76 77     //system("pause");78 }

 

@Author: YouSiki

 

AOJ DSL_2_D Range Update Query (RUQ)


联系
我们