线段树

感觉线段树......有点捉急啊........

很基础的题目~，就只有建树~更新点~和询问~。。。。。。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int MAX=55555;
 7 int a[MAX<<2];
 8 
 9 void build(int l,int r,int x)         //建树
10 {
11     if(l==r)
12     {
13         scanf("%d",&a[x]);
14         return;
15     }
16     int m=(l+r)>>1;
17     build(l,m,x<<1);
18     build(m+1,r,x<<1|1);
19     a[x]=a[x<<1]+a[x<<1|1];
20 }
21 
22 void update(int k,int word,int l,int r,int x)       //更新数据
23 { 
24     if(l==r)
25     {
26         a[x]+=word;
27         return;
28     }
29     int m=(l+r)>>1;
30     if(k<=m) update(k,word,l,m,x<<1);
31     else
32         update(k,word,m+1,r,x<<1|1);
33     a[x]=a[x<<1]+a[x<<1|1];
34 }
35 
36 int query(int le,int ri,int l,int r,int x)       //询问
37 {
38     if(le<=l && ri>=r)
39         return a[x];
40     int m=(l+r)>>1,re=0;
41     if(le<=m) re+=query(le,ri,l,m,x<<1);
42     if(ri>m) re+=query(le,ri,m+1,r,x<<1|1);
43     return re;
44 }
45 
46 int main()
47 {
48     int t,n,cas=0;
49     char str[10];
50     scanf("%d",&t);
51     while(t--)
52     {
53         printf("Case %d:
",++cas);
54         scanf("%d",&n);
55         build(1,n,1);
56         while(~scanf("%s",str))
57         {
58             if(str[0]=='E') break;
59             int a,b;
60             scanf("%d%d",&a,&b);
61             if(str[0]=='Q') printf("%d
",query(a,b,1,n,1));
62             else
63                 if(str[0]=='S') update(a,-b,1,n,1);
64             else
65                 update(a,b,1,n,1);
66         }
67     }
68     return 0;
69 }

//memory：748KB time：218ms

hdu1754 I Hate It

代码：

感觉这道题和前面的那道很相似~~~

  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 
  5 #define MAX_N 200000
  6 int big;
  7 
  8 class Node
  9 {
 10 public:
 11     int left,right,data, maxx;
 12 }stu[MAX_N*4];
 13 
 14 int Max(int a,int b)
 15 {
 16     return a>b?a:b;
 17 }
 18 
 19 void CreateTree(int i,int a,int b)
 20 {
 21     stu[i].left = a;
 22     stu[i].right = b;
 23     stu[i].maxx = 0;
 24     stu[i].data = 0;
 25     if(a == b)
 26         return;
 27     else
 28     {
 29         int mid = (a+b)/2;
 30         CreateTree(i*2,a,mid);
 31         CreateTree(i*2+1,mid+1,b);
 32     }
 33 }
 34 
 35 void updata(int i,int a,int b)
 36 {
 37     if(stu[i].left==a && stu[i].right==a)
 38     {
 39         stu[i].data = b;
 40         stu[i].maxx = b;
 41     }
 42     else
 43     {
 44         int mid=(stu[i].left+stu[i].right)/2;
 45         if(a<=mid)
 46             updata(i*2,a,b);
 47         else
 48             updata(i*2+1,a,b);
 49         if(b>stu[i].maxx)
 50             stu[i].maxx=b;
 51     }
 52 }
 53 
 54 void find(int i,int a,int b)
 55 {
 56     if(stu[i].left == a && stu[i].right == b)
 57     {
 58         if(stu[i].maxx > big)
 59             big = stu[i].maxx;
 60     }
 61     else
 62     {
 63         int mid = (stu[i].left + stu[i].right)/2;
 64         if(b <= mid)
 65         {
 66             find(i*2,a,b);
 67         }
 68         else if(a > mid)
 69         {
 70             find(i*2+1,a,b);
 71         }
 72         else
 73         {
 74             find(i*2,a,mid);
 75             find(i*2+1,mid+1,b);
 76         }
 77     }
 78 }
 79 
 80 int main()
 81 {
 82     int n,m,num;
 83     int i;
 84 
 85     while(scanf("%d%d",&n,&m)!=EOF)
 86     {
 87         CreateTree(1,1,n);
 88         for(i=1;i<=n;i++)
 89         {
 90             scanf("%d",&num);
 91             updata(1,i,num);
 92         }
 93         char c;
 94         int x1,x2;
 95         while(m--)
 96         {
 97             scanf("%*c%c",&c);
 98             scanf("%d%d",&x1,&x2);
 99             if(c == 'Q')
100             {
101                 big = 0x80000000;
102                 find(1,x1,x2);
103                 printf("%d
",big);
104             }
105             else
106                 updata(1,x1,x2);
107         }
108     }
109     return 0;
110 }

View Code

//memory:8452KB time:1093ms

尼玛........用a>b?a:b;居然超时.......直接用max()函数就木有超时........T T

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAX=222222;
 7 int a[MAX<<2];
 8 
 9 void build(int l,int r,int x)
10 {
11     if(l==r)
12     {
13         scanf("%d",&a[x]);
14         return;
15     }
16     int m=(l+r)>>1;
17     build(l,m,x<<1);
18     build(m+1,r,x<<1|1);
19     a[x]=max(a[x<<1],a[x<<1|1]);
20 }
21 
22 void update(int p,int w,int l,int r,int x)
23 {
24     if(l==r)
25     {
26         a[x]=w;
27         return;
28     }
29     int m=(l+r)>>1;
30     if(p<=m) update(p,w,l,m,x<<1);
31     if(p>m) update(p,w,m+1,r,x<<1|1);
32     a[x]=max(a[x<<1],a[x<<1|1]);
33 }
34 
35 int query(int le,int ri,int l,int r,int x)
36 {
37     if (le<=l && r<=ri)
38         return a[x];
39     int m = (l + r) >> 1;
40     int re=0;
41     if(le<=m) re=max(re,query(le,ri,l,m,x<<1));
42     if(ri>m) re=max(re,query(le,ri,m+1,r,x<<1|1));
43     return re;
44 }
45 
46 int main()
47 {
48     int m,n;
49     char str[2];
50     while(~scanf("%d%d",&m,&n))
51     {
52         build(1,m,1);
53         while(n--)
54         {
55             int a,b;
56             scanf("%s",str);
57             scanf("%d%d",&a,&b);
58             if(str[0]=='Q') printf("%d
",query(a,b,1,m,1));
59             else
60                 update(a,b,1,m,1);
61         }
62     }
63     return 0;
64 }

//memory:2284KB time:500ms

hdu1394 Minimum Inversion Number

题意：就是给出一串有序数列，你可以将数列（a0,a1,...,an）的首个数字（a0）移到数列最后面~可以移动n次，问在这些数列中最小的inversion number是多少~

PS：inversion number是——如ai与aj,其中i<j但ai>aj。

【注】题中可以知道：当求出了最初数列的inversion number数（sum），那么当把a[i]移动到队尾时，此时的inversion number为sum=sum+n-1+a[i]+a[i]。（这个结论很容易得出的~~~）

方法一：暴力求解~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int a[10050];
 7 
 8 int main()
 9 {
10     int n,i,j,re,sum,k;
11     while(~scanf("%d",&n))
12     {
13          for(i=0;i<n;i++)
14         {
15             scanf("%d",&a[i]);
16             a[i+n]=a[i];
17         }
18         sum=0;
19         for(j=0;j<n;j++)
20         {
21             for(k=j+1;k<n;k++)
22                 if(a[k]<a[j])
23                     sum++;
24         }
25         re=sum;
26         for(i=0;i<n;i++)
27         {
28             sum+=n-1-2*a[i];
29             re=min(sum,re);
30         }
31         printf("%d
",re);
32 
33     }
34     return 0;
35 }

View Code

//memory：268KB time:265ms

方法二：当然就是线段树啦~，先求出出数列的inversion number，再用上面讲到的公式求其他的inversion number~~~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAX=5555;
 7 int a[MAX<<2];
 8 
 9 void build(int l,int r,int x)
10 {
11     a[x]=0;
12     if(l==r) return;
13     int m=(l+r)>>1;
14     build(l,m,x<<1);
15     build(m+1,r,x<<1|1);
16 }
17 
18 void update(int p,int l,int r,int x)
19 {
20     if(l==r)
21     {
22         a[x]++;
23         return;
24     }
25     int m=(l+r)>>1;
26     if(p<=m) update(p,l,m,x<<1);
27     else
28         update(p,m+1,r,x<<1|1);
29     a[x]=a[x<<1]+a[x<<1|1];
30 }
31 
32 int query(int le,int ri,int l,int r,int x)
33 {
34     if(le<=l && r<=ri)
35         return a[x];
36     int m=(l+r)>>1;
37     int re=0;
38     if(le<=m) re+=query(le,ri,l,m,x<<1);
39     if(ri>m) re+=query(le,ri,m+1,r,x<<1|1);
40     return re;
41 }
42 
43 int x[MAX];
44 int main()
45 {
46     int n;
47     while(~scanf("%d",&n))
48     {
49         build(0,n-1,1);
50         int sum=0;
51         for(int i=0;i<n;i++)              //输入出数列，并求出出数列的inversion number~
52         {
53             scanf("%d",&x[i]);
54             sum+=query(x[i],n-1,0,n-1,1);
55             update(x[i],0,n-1,1);
56         }
57         int re=sum;
58         for(int i=0;i<n;i++)
59         {
60             sum+=n-x[i]-x[i]-1;
61             re=min(re,sum);              //找出最小的inversion number~
62         }
63         printf("%d
",re);
64     }
65     return 0;
66 }

//memory:280KB time:46ms

hdu2795 Billboard

......