UVA12299 线段树水水水,但别乱开空间= =

Posted by Cww97 on 2016-03-08

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50831413
题目

看lyc的题解。。。。
传送门
果然神的题解都不放代码的

但是一直不知道为什么错了。。。后来也不知道怎么改就过了。。。。
后来慢慢改,也不知道怎么就ac了。。。
看来敲线段树还是要仔细啊。啊啊啊啊啊啊啊啊啊啊啊啊啊

单点修改,区间查询,练练非递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=433333,INF=99999999;

struct tree{
int T[N],BTM;

void build(int n){
BTM=1; while (BTM<n)BTM<<=1; BTM--;//getBTM
for (int i=BTM+1;i<=BTM+n;i++)scanf("%d",&T[i]);
scanf("\n");
for (int i=BTM+n+1;i<=BTM*2+1;i++)T[i]=INF;
for (int i=BTM;i>=1;i--){
T[i]=min(T[i<<1],T[i<<1^1]);
}
}

int query(int l,int r){
int ans=INF;
for (l+=BTM-1,r+=BTM+1;l^r^1;l>>=1,r>>=1){
if (~l&1)ans=min(ans,T[l^1]);
if ( r&1)ans=min(ans,T[r^1]);
}
return ans;
}

void change(int k,int x){
for (T[k+=BTM]=x,k>>=1;k;k>>=1){
T[k]=min(T[k<<1],T[k<<1^1]);
}
}
}T;

int main(){
int x,y,n,q;
//freopen("fuck.in","r",stdin);
scanf("%d%d",&n,&q);
T.build(n);

char ch,ch2,ask;
while (q--){
scanf("%c",&ask);
for (int i=1;i<=5;i++)scanf("%c",&ch);
if (ask=='q'){
scanf("%d%c%d%c",&x,&ch,&y,&ch2);
printf("%d\n",T.query(x,y));
}else {
scanf("%d%c",&x,&ch);
int tmp=T.T[x+T.BTM];
while (~scanf("%d%c",&y,&ch)){
T.change(x,T.T[y+T.BTM]);
x=y; if (ch==')')break;
}
T.change(y,tmp);
}
getchar();
}
return 0;
}

有没有神犇求教区间修改的非递归写法,,,傻傻看不懂

感谢【爱晒妹的静静】帮我普及基本法
这里写图片描述

啊啊啊啊啊
一开始数组开20W,然后RTE,
一怒之下开200W,,,SE
最后改成40W,,,,,A了,,
十分的狗屁不通