1: #include
      

2: #include
      

3: #include
      

4: using namespace std;

5: int m,n;

6: const int maxn=100000;

7: int w[maxn],f[maxn*50];

8: void get_prepare()

9: {

10:     memset(w,0,sizeof(w));

11:     memset(f,0,sizeof(f));

12:     cin >> m >> n;

13:     for (int i=1;i<=m;i++) cin >> w[i];

14: }

15: void build_tree(int a,int b,int p)

16: {

17:     if (a==b){

18:         f[p]=w[a];

19:         return;

20:     }

21:     int k=(a+b)/2;

22:     build_tree(a,k,p*2);

23:     build_tree(k+1,b,p*2+1);

24:     f[p]=min(f[p*2],f[p*2+1]);

25: }

26: int ask_tree(int a,int b,int l,int r,int p)

27: {

28:     if (a==l && b==r) return f[p];

29:     int k=(l+r)/2;

30:     if (b<=k) return ask_tree(a,b,l,k,p*2);

31:     if (a>k) return ask_tree(a,b,k+1,r,p*2+1);

32:     return min(ask_tree(a,k,l,k,p*2),ask_tree(k+1,b,k+1,r,p*2+1));

33: }

34: void update(int a,int l,int r,int p)

35: {

36:     if (l==r){

37:         f[p]=w[l];

38:         return;

39:     }

40:     int k=(l+r)/2;

41:     if (a<=k) update(a,l,k,p*2);

42:     else update(a,k+1,r,p*2+1);

43:     f[p]=min(f[p*2],f[p*2+1]);

44: }

45: void change(int x,int y){

46:     w[x]=y;

47:     update(x,1,m,1);

48: }

49: int main()

50: {

51:     get_prepare();

52:     build_tree(1,m,1);

53:     int x,y,p;

54:     for (int i=0;i

55:         cin >> p >> x >> y;

56:         if (p==1) cout << ask_tree(x,y,1,m,1) << ' ';

57:         else change(x,y);

58:     }

59:     cout << endl;

60:     return 0;

61: }

1. 我想说 在main()里的 那个if-else是被迫改的，原本是p==1?cout << ask_tree(x,y,1,m,1) << ' ':change(x,y);可是不知道为什么在自己机器可以运行，交到tyvj会CE，为通过率泪奔……

2. 对于这个线段树的思想…  不阐述了，好歹没有忘掉哈

3. 我把树的数组开到5*10^6才把最后后两组数据过掉， 再次泪奔……