当前位置：首页 > news >正文

UVa 12769 Kool Konstructions

news 2026/7/26 10:01:04

题目描述

市议会希望增加主要街道上建筑物的高度以吸引更多商业，但担心建设过快会导致资金耗尽，因此他们计划分阶段建设。

假设街道长度为nnn个单位，每个建筑物宽度为111个单位。在每个阶段，议会会选择两个端点（1≤a≤b≤100,0001 \leq a \leq b \leq 100,0001≤a≤b≤100,000），并将区间[a,b][a, b][a,b]内每栋建筑物的高度增加yyy个单位。例如，下面是变更前后的城市天际线：a=2,b=10,y=1a=2, b=10, y=1a=2,b=10,y=1。

随时间推移，跟踪建筑物高度变得相当复杂，因此需要你的帮助。

输入格式

输入文件最多包含888个测试用例。每个测试用例的第一行是一个正整数TTT，表示指令数量。接下来的TTT行（T≤100,000T \leq 100,000T≤100,000）是以下两种格式之一：

B a b y：建造指令 —— 将区间[a,b][a, b][a,b]内每栋建筑的高度增加yyy单位。
Q a：查询指令 —— 输出此时建筑aaa的高度。

输入行总是合法的，即1≤a≤b≤100,0001 \leq a \leq b \leq 100,0001≤a≤b≤100,000。yyy是正整数，最多为1,0001,0001,000。假设在第一个阶段之前，所有建筑的高度均为000。输入以T=0T=0T=0结束。

输出格式

对于每个测试用例的每个查询指令，在一行中输出指定建筑的高度。

样例

输入

9 B 5 5 2 B 8 8 2 B 10 13 1 Q 8 B 8 13 1 Q 8 B 15 16 1 B 2 10 1 Q 8 0

输出

2 3 4

题目分析

本题的核心是：维护一个长度为100,000100,000100,000的数组（初始全为000），支持两种操作：

区间加：将区间[a,b][a, b][a,b]内的所有元素增加yyy。
单点查询：查询位置aaa的当前值。

直接模拟：对于每个B指令，遍历区间[a,b][a, b][a,b]逐个增加，时间复杂度为O(T⋅n)O(T \cdot n)O(T⋅n)，其中nnn为区间长度，最坏情况下n=105n=10^5n=105，T=105T=10^5T=105，总操作量可达101010^{10}1010，不可接受。

我们需要一种支持高效区间更新和单点查询的数据结构。

解题思路

差分数组 + 前缀和

差分数组的思想：设原数组为height[1..n]\textit{height}[1..n]height[1..n]，定义差分数组diff[i]=height[i]−height[i−1]\textit{diff}[i] = \textit{height}[i] - \textit{height}[i-1]diff[i]=height[i]−height[i−1]（约定height[0]=0\textit{height}[0]=0height[0]=0）。那么：

对原数组区间[a,b][a, b][a,b]增加yyy，等价于：
- diff[a] +=y\textit{diff}[a] \ += ydiff[a]+=y
- diff[b+1] −=y\textit{diff}[b+1] \ -= ydiff[b+1]−=y
查询原数组位置aaa的值，等价于求diff[1..a]\textit{diff}[1..a]diff[1..a]的前缀和：height[a]=∑i=1adiff[i]\textit{height}[a] = \sum_{i=1}^{a} \textit{diff}[i]height[a]=∑i=1adiff[i]

这样，每次更新是O(1)O(1)O(1)的，但查询需要O(n)O(n)O(n)计算前缀和，当查询很多时仍会超时。

树状数组（Fenwick Tree\texttt{Fenwick Tree}Fenwick Tree）

树状数组支持单点加和前缀和查询，均为O(log⁡n)O(\log n)O(logn)。结合差分思想：

区间加[a,b][a, b][a,b]增加yyy：执行两次单点加：add(a, y)和add(b+1, -y)
单点查询aaa：执行前缀和查询sum(a)

这样每次操作均为O(log⁡N)O(\log N)O(logN)，N=100,000N=100,000N=100,000，总复杂度O(Tlog⁡N)O(T \log N)O(TlogN)，完全可接受。

算法流程

初始化大小为100,002100,002100,002的树状数组（因为b+1b+1b+1可能等于100,001100,001100,001）。
对于每个测试用例：
- 读入TTT，若T=0T=0T=0则结束。
- 循环TTT次：
  - 读入指令类型。
  - 若为B，读入a,b,ya,b,ya,b,y，执行add(a, y)和add(b+1, -y)。
  - 若为Q，读入aaa，输出sum(a)。
每个测试用例结束后，重置树状数组（或直接覆盖）。

复杂度分析

时间复杂度：每个操作O(log⁡N)O(\log N)O(logN)，总操作次数T≤105T \leq 10^5T≤105，故总复杂度O(Tlog⁡N)O(T \log N)O(TlogN)。
空间复杂度：O(N)O(N)O(N)，N=100,002N=100,002N=100,002。

代码实现

// Kool Konstructions// UVa ID: 12769// Verdict: Accepted// Submission Date: 2026-06-04// UVa Run Time: 0.080s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_N=100002;intbit[MAX_N];// 树状数组// 单点加voidadd(intidx,intval){while(idx<MAX_N){bit[idx]+=val;idx+=idx&-idx;}}// 前缀和intsum(intidx){intres=0;while(idx>0){res+=bit[idx];idx-=idx&-idx;}returnres;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;while(cin>>T&&T!=0){memset(bit,0,sizeof(bit));// 每个测试用例重置树状数组while(T--){charop;cin>>op;if(op=='B'){inta,b,y;cin>>a>>b>>y;add(a,y);add(b+1,-y);}else{// op == 'Q'inta;cin>>a;cout<<sum(a)<<'\n';}}}return0;}