植树节，种种小树苗就好了。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define MAXM 100000
 5 #define lson l , m , rt<<1
 6 #define rson m+1 , r , rt<<1|1
 7 
 8 int minv[MAXM<<2],n,m;
 9 
10 
11 void pushup(int rt)
12 {
13     minv[rt] = min(minv[rt<<1] , minv[rt<<1|1]);
14 }
15 
16 
17 void build(int l,int r,int rt)
18 {
19     if(l == r){
20         scanf("%d",&minv[rt]);
21         return ;
22     }
23     int m = (l+r) >> 1;
24     build(lson);
25     build(rson);
26     pushup(rt);
27 }
28 
29 
30 int query(int L,int R,int l,int r,int rt)
31 {
32     if(L<=l && r<=R) return minv[rt];
33     int m = (l+r) >> 1;
34     int ret = 2e9;
35     if(L <= m) ret = min(ret , query(L,R,lson));
36     if(R > m) ret = min(ret , query(L,R,rson));
37     return ret;
38 }
39 
40 
41 void work()
42 {
43     int a,b;
44     for(int i = 1 ; i <= n ; i++)
45     {
46         scanf("%d%d",&a,&b);
47         printf("%d%s",query(a,b,1,m,1) , i<n ? " ":"\n");
48     }
49 }
50 
51 
52 void init()
53 {
54     scanf("%d%d",&m,&n);
55     build(1,m,1);
56 }
57 
58 
59 int main()
60 {
61     init();
62     work();
63     return 0;
64 }

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define MAXN 200010
 7 #define LL long long
 8 
 9 int n,a[MAXN];
10 int b[MAXN],x[MAXN];
11 
12 
13 int sum(int k)
14 {
15     int ret = 0;
16     while(k > 0)
17     {
18         ret += b[k];
19         k -= k&-k;
20     }
21     return ret;
22 }
23 
24 
25 void add(int k)
26 {
27     while(k <= n)
28     {
29         b[k]++;
30         k += k&-k;
31     }
32 }
33 
34 
35 void work()
36 {
37     LL ans1 = 0,ans2 = 0;
38     for(int i = 1 ; i <= n ; i++)
39     {
40         x[i] = sum(a[i]-1);
41         add(a[i]);
42     }
43     for(int i = 2 ; i < n ; i++)
44     {
45         ans1 += (i - 1 - x[i]) * (n - i - a[i] + 1 + x[i]);
46         ans2 += x[i] * (a[i] - 1 - x[i]);
47     }
48     printf("%lld %lld\n",ans1 , ans2);
49 }
50 
51 
52 void init()
53 {
54     scanf("%d",&n);
55     for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
56 }
57 
58 
59 int main()
60 {
61     init();
62     work();
63     return 0;
64 }