|
B
|
Potentiometers
Input: Standard Input
Output:
Standard Output
|
A potentiometer, or potmeter for short, is an
electronic device with a variable electric resistance. It has two terminals and
some kind of control mechanism (often a dial, a wheel or a slide) with which
the resistance between the terminals can be adjusted from zero (no resistance)
to some maximum value. Resistance is measured in Ohms, and when two or more
resistors are connected in series (one after the other, in a row), the total
resistance of the array is the sum of the resistances of the individual
resistors.
In this problem we will consider an array of N
potmeters, numbered 1 to N from left to right. The left terminal
of some potmeter numbered x is connected to the right terminal of
potmeter x-1, and its right terminal to the left terminal of potmeter x+1.
The left terminal of potmeter 1 and the right terminal of potmeter N
are not connected.
Initially all the potmeters are set to some value
between 0 and 1000 Ohms. Then we can do two things:
- Set one of the potmeters to another
value.
- Measure the resistance between
two terminals anywhere in the array.
Input
The input consists less than 3
cases. Each case starts with N, the number of potmeters in the array, on
a line by itself. N can be as large as 200000. Each of next N lines
contains one numbers between 0 and 1000, the initial resistances of the
potmeters in the order 1 to N. Then follow a number of actions,
each on a line by itself. The number of actions can be as many as 200000. There
are three types of action:
- "S x r" - set
potmeter x to r Ohms. x is a valid potmeter number
and r is between 0 and 1000.
- "M x y" - measure the
resistance between the left terminal of potmeter x and the right
terminal of potmeter y. Both numbers will be valid and x is
smaller than or equal to y.
- "END" - end of this
case. Appears only once at the end of a list of actions.
A case with N=0 signals
the end of the input and it should not be processed.
Output
For each case in the input produce
a line "Case n:", where n is the case number, starting from 1.
For each measurement in the input, output a line containing one number: the
measured resistance in Ohms. The actions should be applied to the array of
potmeters in the order given in the input.
Print a blank line between cases.
Warning: Input Data is pretty
big (~ 8 MB) so use faster IO.
Sample Input
Output for Sample Input
|
3
100
100
100
M
1 1
M
1 3
S
2 200
M
1 2
S
3 0
M
2 3
END
10
1
2
3
4
5
6
7
8
9
10
M
1 10
END
0
|
Case
1:
100
300
300
200
Case
2:
55
|
Problem setter: Joachim Wulff, Special
Thanks: Shahriar Manzoor
基本上需要兩種操作 (1) 求區間總合 (2) 單點更新
最簡單的遞迴線段樹寫法
#include <stdio.h>
int A[(1<<18)+1], ST[(1<<19)+1];
void setTree(int k, int l, int r) {
if(l == r)
ST[k] = A[l];
else if(l < r) {
int m = (l+r)>>1;
setTree(k<<1, l, m);
setTree(k<<1|1, m+1, r);
ST[k] = ST[k<<1] + ST[k<<1|1];
} else
ST[k] = 0;
}
int query(int k, int l, int r, int &x, int &y) {
if(l > r) return 0;
if(x <= l && r <= y)
return ST[k];
int m = (l+r)>>1;
if(y <= m)
return query(k<<1, l, m, x, y);
else if(x > m)
return query(k<<1|1, m+1, r, x, y);
else
return query(k<<1, l, m, x, y)+
query(k<<1|1, m+1, r, x, y);
}
void modify(int k, int l, int r, int &x, int &y) {
if(l > r) return ;
if(l == r && l == x) {
ST[k] = y;
return;
}
int m = (l+r)>>1;
if(x <= m)
modify(k<<1, l, m, x, y);
else
modify(k<<1|1, m+1, r, x, y);
if(l != r)
ST[k] = ST[k<<1] + ST[k<<1|1];
}
int main() {
int n, x, y, i;
int cases = 0;
char op[10], cmd[50];
while(scanf("%d", &n) == 1 && n) {
for(i = 1; i <= n; i++)
scanf("%d", &A[i]);
while(getchar() != '\n');
setTree(1, 1, n);
if(cases) puts("");
printf("Case %d:\n", ++cases);
while(gets(cmd)) {
if(cmd[0] == 'E')
break;
sscanf(cmd, "%s %d %d", op, &x, &y);
if(op[0] == 'M')
printf("%d\n", query(1, 1, n, x, y));
else
modify(1, 1, n, x, y);
}
}
return 0;
}
zkw 線段樹寫法#include <stdio.h>
#include <string.h>
#define node 262144
int A[node], tree[node<<1], M;
void setTree() {
int i;
for(i = 2*M-1; i > 0; i--) {
if(i >= M) { //leaf
tree[i] = A[i-M];
} else {
tree[i] = tree[i<<1]+tree[(i<<1)+1];
}
}
}
int query(int s, int t) {
static int i;
int ans = 0;
for(s = s+M-1, t = t+M+1; (s^t) != 1;) {
if(~s&1)
ans += tree[s^1];
if(t&1)
ans += tree[t^1];
s >>= 1, t >>= 1;
}
return ans;
}
void singleModify(int s, int v) {
s += M;
while(s) {
tree[s] += v;
s >>= 1;
}
}
int main() {
int n, x, y, i;
int cases = 0;
char op[10], cmd[50];
while(scanf("%d", &n) == 1 && n) {
for(M = 1; M < n+2; M <<= 1);
memset(A, 0, sizeof(A));
for(i = 1; i <= n; i++)
scanf("%d", &A[i]);
while(getchar() != '\n');
if(cases) puts("");
printf("Case %d:\n", ++cases);
setTree();
while(gets(cmd)) {
if(cmd[0] == 'E')
break;
sscanf(cmd, "%s %d %d", op, &x, &y);
if(op[0] == 'M')
printf("%d\n", query(x, y));
else {
singleModify(x, y-A[x]);
A[x] = y;
}
}
}
return 0;
}
直接換個資料結構 binary indexed tree 掃一次。
速度跟 zkw 差不多。
#include <stdio.h>
int BIT[(1<<18)+1], A[1<<18];
int query(int idx) {
static int sum;
sum = 0;
while(idx) {
sum += BIT[idx];
idx -= idx&(-idx);
}
return sum;
}
void modify(int idx, int L, int v) {
while(idx <= L) {
BIT[idx] += v;
idx += idx&(-idx);
}
}
int main() {
int n, x, y, i;
int cases = 0;
char op[10], cmd[50];
while(scanf("%d", &n) == 1 && n) {
for(i = 1; i <= n; i++) {
scanf("%d", &A[i]);
BIT[i] = 0;
}
for(i = 1; i <= n; i++)
modify(i, n, A[i]);
while(getchar() != '\n');
if(cases) puts("");
printf("Case %d:\n", ++cases);
while(gets(cmd)) {
if(cmd[0] == 'E')
break;
sscanf(cmd, "%s %d %d", op, &x, &y);
if(op[0] == 'M')
printf("%d\n", query(y) - query(x-1));
else {
modify(x, n, y-A[x]);
A[x] = y;
}
}
}
return 0;
}
文章定位：
