#P2883. gss2加强版

    ID: 1990 传统题 1000ms 512MiB 尝试: 270 已通过: 41 难度: 8 上传者: 标签>CF2400提高+/省选-二维树状数组有序集合离线预收集坐标局部离散化离散化增量维护

gss2加强版

题目描述

维护一个 nn 个数的序列 aa,要求支持 qq 次以下操作:

  • U x y,ax←ya_x\gets y;
  • Q x y,求 ax⋯ya_{x\cdots y} 去重后的和。

输入格式

第一行一个整数 nn。

第二行 nn 个整数表示 a1⋯na_{1\cdots n}。

第三行一个整数 qq。

接下来 qq 行每行一个操作,格式见题目描述。

输出格式

对于每个询问操作,输出一行一个整数表示答案。

5
1 2 4 2 3 
3
Q 2 4
U 4 7
Q 2 4
6
13

数据规模与约定

对于 30%30\% 的数据,1≤n,q≤3×1031\leq n,q\leq 3\times 10^3;

对于 100%100\% 的数据,1≤n,q≤1051\leq n,q\leq 10^5,aia_i 始终在 int 范围内。