Ubuntu Intrepid -- Xen Dom0 + DomU 搞定！
whuacm - oak - warmupII
Mar
8
uva - 2191 - Potentiometers 
抽象题意：给出最多200,000个不超过1000的非负整数，对最多200,000次以下两类操作进行处理
1. M x y ——求第x到第y个整数之间的所有整数的和。
2. S x v ——将第x个整数的值置为v。
显然，硬搞要TLE的，稍微想了一下，就知道应该用线段树(或者树状数组?)来完成。
关于线段树可以参考 http://acm.whu.edu.cn/blog/read.php?26 以及 http://acm.whu.edu.cn/blog/read.php?51
简单的说，就是用一个平衡二叉树来存储这些东西，
每个叶节点存放一个整数(一个单位"线段")，
而每个分支节点存放的是一条"线段"
在M操作的时候，只要递归地将线段xy分割，能够在logN的时间内查询出
在S操作的时候，只要递归地找到对应的叶节点更新，并在返回的时候一层层更新涉及到的分支节点即可，也是logN。
好久没有写稍长的代码了，这个线段树的具体实现也忘得差不多了，还是去翻了一下yyt的论文。
不过这次写得顺利多了，思路比较清晰。
具体的代码为
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
1. M x y ——求第x到第y个整数之间的所有整数的和。
2. S x v ——将第x个整数的值置为v。
显然，硬搞要TLE的，稍微想了一下，就知道应该用线段树(或者树状数组?)来完成。
关于线段树可以参考 http://acm.whu.edu.cn/blog/read.php?26 以及 http://acm.whu.edu.cn/blog/read.php?51
简单的说，就是用一个平衡二叉树来存储这些东西，
每个叶节点存放一个整数(一个单位"线段")，
而每个分支节点存放的是一条"线段"
在M操作的时候，只要递归地将线段xy分割，能够在logN的时间内查询出
在S操作的时候，只要递归地找到对应的叶节点更新，并在返回的时候一层层更新涉及到的分支节点即可，也是logN。
好久没有写稍长的代码了，这个线段树的具体实现也忘得差不多了，还是去翻了一下yyt的论文。
不过这次写得顺利多了，思路比较清晰。
具体的代码为
#include<stdio.h>
struct node{
int l, m, r, v;
} tree[1000100];
int res[200100];
void make(int l, int r, int i = 1){
tree[i].l = l;
tree[i].r = r;
tree[i].m = (l + r) / 2;
if(l == r){
tree[i].v = res[l];
return;
}else{
make(l, tree[i].m, 2 * i);
make(tree[i].m + 1, r, 2 * i + 1);
tree[i].v = tree[2*i].v + tree[2*i+1].v;
}
}
void insert(int n, int v, int i = 1){
if(tree[i].l == tree[i].r && tree[i].l == n){
tree[i].v = v;
}else{
if(n <= tree[i].m){
insert(n, v, 2 * i);
}else{
insert(n, v, 2 * i + 1);
}
tree[i].v = tree[2*i].v + tree[2*i+1].v;
}
}
int count(int l, int r, int i = 1){
if(tree[i].l == l && tree[i].r == r){
return tree[i].v;
}else{
if(r <= tree[i].m){
return count(l, r, 2 * i);
}else if(l > tree[i].m){
return count(l, r, 2 * i + 1);
}else{
return count(l, tree[i].m, 2 * i)
+ count(tree[i].m + 1, r, 2 * i + 1);
}
}
}
void setv(){
int n, v;
scanf("%d%d", &n, &v);
insert(n, v);
}
void measure(){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", count(l, r));
}
int main(){
int casec = 1, N, first = 1;
char t;
while(scanf("%d", &N), N != 0){
if(first) first = 0;
else putchar('\n');
for(int i = 1; i <= N; ++i) scanf("%d", res+i);
getchar();
printf("Case %d:\n", casec++);
make(1, N);
while(true){
t = getchar();
if(t == 'M') measure();
else if(t == 'S') setv();
else if(t == 'E') {
while(t = getchar(), t != '\n' && t != EOF);
break;
}
while(t = getchar(), t != '\n' && t != EOF);
}
}
return 0;
}
struct node{
int l, m, r, v;
} tree[1000100];
int res[200100];
void make(int l, int r, int i = 1){
tree[i].l = l;
tree[i].r = r;
tree[i].m = (l + r) / 2;
if(l == r){
tree[i].v = res[l];
return;
}else{
make(l, tree[i].m, 2 * i);
make(tree[i].m + 1, r, 2 * i + 1);
tree[i].v = tree[2*i].v + tree[2*i+1].v;
}
}
void insert(int n, int v, int i = 1){
if(tree[i].l == tree[i].r && tree[i].l == n){
tree[i].v = v;
}else{
if(n <= tree[i].m){
insert(n, v, 2 * i);
}else{
insert(n, v, 2 * i + 1);
}
tree[i].v = tree[2*i].v + tree[2*i+1].v;
}
}
int count(int l, int r, int i = 1){
if(tree[i].l == l && tree[i].r == r){
return tree[i].v;
}else{
if(r <= tree[i].m){
return count(l, r, 2 * i);
}else if(l > tree[i].m){
return count(l, r, 2 * i + 1);
}else{
return count(l, tree[i].m, 2 * i)
+ count(tree[i].m + 1, r, 2 * i + 1);
}
}
}
void setv(){
int n, v;
scanf("%d%d", &n, &v);
insert(n, v);
}
void measure(){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", count(l, r));
}
int main(){
int casec = 1, N, first = 1;
char t;
while(scanf("%d", &N), N != 0){
if(first) first = 0;
else putchar('\n');
for(int i = 1; i <= N; ++i) scanf("%d", res+i);
getchar();
printf("Case %d:\n", casec++);
make(1, N);
while(true){
t = getchar();
if(t == 'M') measure();
else if(t == 'S') setv();
else if(t == 'E') {
while(t = getchar(), t != '\n' && t != EOF);
break;
}
while(t = getchar(), t != '\n' && t != EOF);
}
}
return 0;
}
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
