bet365娱乐场官网 区间颜色  0 表示黑  1 象征白  -1表示不管标志。每个营地初始各出若干人。

题意:给您n个圆球败成一行,初始都为黑色,现在深受有操作(L,R,color),给[L,R]间隔内的求染上颜色color,’w’为白,’b’为不法。问最后极丰富的白色区间的起点与终端的岗位。

1、hdu 1166 敌兵布阵(★☆☆☆☆)

解法:先离散化,为了防范离散后错误,不仅以L,R离散,还要在L+1,L-1,R+1,R-1一起离散,这样就算不用会发生问题了。然后打线段树,线段树护四只价:

  题意:有n个基地,每个营地初始各发生若干人数,每次询问[l,r]营地的终究人数,或者对有营地加上要减去多口。

1.col
 区间颜色  0 表示黑  1 表示白  -1表示不管标志

  思路:线段树单点更新,区间查询

2.maxi
区里内最好酷白区间的尺寸,由于白色用1象征,所以最好充分白区间的长度就为距离极要命连续与

bet365娱乐场官网 1bet365娱乐场官网 2

3.lmax
从距离左端开始之极端老白区间长

 1 //线段树单点更新,区间查询
 2 #include<iostream>
 3 using namespace std;
 4 const int maxn = 50010;
 5 int N;
 6 int barracks[maxn];
 7 int Tree[4 * maxn];
 8 void Create(int root,int l,int r)
 9 {
10     if (l == r)
11     {
12         Tree[root] = barracks[l];
13         return;
14     }
15     int mid = (l + r) / 2;
16     Create(root * 2 + 1, l, mid);
17     Create(root * 2 + 2, mid + 1, r);
18     Tree[root] = Tree[root * 2 + 1] + Tree[root * 2 + 2];
19 }
20 void Update(int root, int l, int r, int pos, int v)
21 {//在第i个营地加上v个人
22     if (l > pos || r < pos) return;
23     else if (l == r&&l == pos)
24     {
25         Tree[root] += v;
26         return;
27     }
28     else
29     {
30         int mid = (l + r) / 2;
31         Update(root * 2 + 1, l, mid, pos, v);
32         Update(root * 2 + 2, mid+1, r, pos, v);
33         Tree[root] = Tree[root * 2 + 1] + Tree[root * 2 + 2];
34     }
35 }
36 int Query(int root, int l, int r, int ll, int rr)
37 {//查询区间ll~rr的总人数
38     if (l > rr || r < ll) return 0;
39     else if (r <= rr&&l >= ll) return Tree[root];
40     else
41     {
42         int mid = (l + r) / 2;
43         return Query(root * 2 + 1, l, mid, ll, rr) + Query(root * 2 + 2, mid + 1, r, ll, rr);
44     }
45 }
46 int main()
47 {
48     int T;
49     int k = 1;
50     scanf("%d", &T);
51     while (T--)
52     {
53         memset(Tree, 0, sizeof(Tree));
54         scanf("%d", &N);
55         for (int i = 0; i < N; i++) scanf("%d",&barracks[i]);
56         Create(0, 0, N - 1);
57         char op[10];
58         printf("Case %d:\n", k);
59         while (scanf("%s", op))
60         {
61             if (op[0] == 'E')
62             {
63                 break;
64             }
65             else if (op[0] == 'A')
66             {
67                 int i, j;
68                 scanf("%d%d", &i, &j);
69                 Update(0, 0, N - 1, i - 1, j);
70             }
71             else if (op[0] == 'S')
72             {
73                 int i, j;
74                 scanf("%d%d", &i, &j);
75                 j = -j;
76                 Update(0, 0, N - 1, i - 1, j);
77             }
78             else
79             {
80                 int i, j;
81                 scanf("%d%d", &i, &j);
82                 printf("%d\n", Query(0, 0, N - 1, i-1, j-1));
83             }
84         }
85         k++;
86     }
87     return 0;
88 }

4.rmax
从距离右端开始的卓绝酷白区间长

View Code

下一场更新,查询,就跟一般求区间连续最要命以及同样了

2、hdu 1754 I Hate It(★☆☆☆☆)

代码:

  题意:有n个学生,每次查询[l,r]次学生的最高分,或者涂改某学生的成就

bet365娱乐场官网 3bet365娱乐场官网 4

  思路:线段树单点更新,区间查询

#include <iostream>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
#define N 14007

struct node
{
    int lmax,rmax,maxi,col;
}tree[4*N];
int num[N],x[N];
int L[2005],R[2005];
char ss[2005][3];
map<int,int> mp;

void pushup(int l,int r,int rt)
{
    tree[rt].lmax = tree[2*rt].lmax;
    tree[rt].rmax = tree[2*rt+1].rmax;
    tree[rt].maxi = max(max(tree[2*rt].maxi,tree[2*rt+1].maxi),tree[2*rt].rmax+tree[2*rt+1].lmax);
    int mid = (l+r)/2;
    int L = x[mid]-x[l-1];  //真实的长度
    int R = x[r]-x[mid];
    if(tree[2*rt].lmax == L)
        tree[rt].lmax += tree[2*rt+1].lmax;
    if(tree[2*rt+1].rmax == R)
        tree[rt].rmax += tree[2*rt].rmax;
}

void pushdown(int l,int r,int rt)
{
    if(tree[rt].col != -1)
    {
        tree[2*rt].col = tree[2*rt+1].col = tree[rt].col;
        int mid = (l+r)/2;
        int L = x[mid]-x[l-1];
        int R = x[r]-x[mid];
        tree[2*rt].maxi = tree[2*rt].lmax = tree[2*rt].rmax = L*tree[rt].col;
        tree[2*rt+1].maxi = tree[2*rt+1].lmax = tree[2*rt+1].rmax = R*tree[rt].col;
        tree[rt].col = -1;
    }
}
void build(int l,int r,int rt)
{
    tree[rt].maxi = tree[rt].lmax = tree[rt].rmax = 0;
    tree[rt].col = -1;
    if(l == r) return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}

void update(int l,int r,int aa,int bb,int col,int rt)
{
    if(aa <= l && bb >= r)
    {
        tree[rt].col = col;
        tree[rt].maxi = tree[rt].lmax = tree[rt].rmax = col*(x[r]-x[l-1]);
        return;
    }
    pushdown(l,r,rt);
    int mid = (l+r)/2;
    if(aa <= mid)
        update(l,mid,aa,bb,col,2*rt);
    if(bb > mid)
        update(mid+1,r,aa,bb,col,2*rt+1);
    pushup(l,r,rt);
}

int query(int l,int r,int rt)
{
    if(l == r) return x[l];
    int mid = (l+r)/2;
    pushdown(l,r,rt);
    if(tree[2*rt].maxi == tree[1].maxi)   //tree[1]  not  tree[rt]
        return query(l,mid,2*rt);
    else if(tree[2*rt].rmax+tree[2*rt+1].lmax == tree[1].maxi)
        return x[mid]-tree[2*rt].rmax+1;
    else
        return query(mid+1,r,2*rt+1);
}

int main()
{
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        mp.clear();
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%s",&L[i],&R[i],ss[i]);
            num[6*i-5] = L[i]-1;
            num[6*i-4] = L[i];
            num[6*i-3] = L[i]+1;
            num[6*i-2] = R[i]-1;
            num[6*i-1] = R[i];
            num[6*i] = R[i]+1;
        }
        sort(num+1,num+6*n+1);
        int ind = unique(num+1,num+6*n+1)-num-1;
        int now = 0;
        x[0] = 0;
        for(i=1;i<=ind;i++)
        {
            x[++now] = num[i];
            mp[num[i]] = now;
        }
        build(1,now,1);
        for(i=1;i<=n;i++)
        {
            int ka = mp[L[i]];
            int kb = mp[R[i]];
            if(ss[i][0] == 'w')
                update(1,now,ka,kb,1,1);
            else
                update(1,now,ka,kb,0,1);
        }
        if(tree[1].maxi <= 0)
            puts("Oh, my god");
        else
        {
            int left = query(1,now,1);
            int right = left+tree[1].maxi-1;
            printf("%d %d\n",left,right);
        }
    }
    return 0;
}

bet365娱乐场官网 5bet365娱乐场官网 6

View Code

 1 //线段树-区间最值,单点更新,区间查询
 2 #include<iostream>
 3 #include<memory.h>
 4 #include<algorithm>
 5 using namespace std;
 6 int n, m;
 7 const int maxn = 200010;
 8 int Score[maxn];
 9 int Tree[4 * maxn];
10 void Create(int root, int l, int r)
11 {
12     if (l == r)
13     {
14         Tree[root] = Score[l];
15         return;
16     }
17     int mid = (l + r) / 2;
18     Create(root * 2 + 1, l, mid);
19     Create(root * 2 + 2, mid + 1, r);
20     Tree[root] = max(Tree[root * 2 + 1], Tree[root * 2 + 2]);
21 }
22 void Update(int root, int l, int r, int pos, int v)
23 {
24     if (l > pos || r < pos) return;
25     else if (l == r&&l == pos)
26     {
27         Tree[root] = v;
28         return;
29     }
30     else
31     {
32         int mid = (l + r) / 2;
33         Update(root * 2 + 1, l, mid, pos, v);
34         Update(root * 2 + 2, mid + 1, r, pos, v);
35         Tree[root] = max(Tree[root * 2 + 1], Tree[root * 2 + 2]);
36     }
37 }
38 int Query(int root, int l, int r, int ll, int rr)
39 {
40     if (l > rr || r < ll) return 0;
41     else if (l >= ll&&r <= rr) return Tree[root];
42     else
43     {
44         int mid = (l + r) / 2;
45         return max(Query(root * 2 + 1, l, mid, ll, rr), Query(root * 2 + 2, mid + 1, r, ll, rr));
46     }
47 
48 }
49 int main()
50 {
51     while (~scanf("%d%d", &n, &m))
52     {
53         memset(Tree, 0, sizeof(Tree));
54         for (int i = 0; i < n; i++) scanf("%d",&Score[i]);
55         char c[5];
56         Create(0, 0, n - 1);
57         for (int i = 0; i < m; i++)
58         {
59             scanf("%s",c);
60             switch (c[0])
61             {
62             case 'Q':
63                 int ll, rr;
64                 scanf("%d%d", &ll, &rr);
65                 printf("%d\n",Query(0,0,n - 1,ll-1,rr-1));
66                 break;
67             case 'U':
68                 int id, v;
69                 scanf("%d%d", &id, &v);
70                 Update(0, 0, n - 1, id - 1, v);
71                 break;
72             }
73         }
74     }
75     return 0;
76 }

 

View Code

3、hdu1394 Minimum Inversion Number(★★★☆☆)

  题意:给出0~n-1这些往往之一个排,然后每次可把首只厕最后,共n个排列。求这些排列着逆序对的极端小值

  思路:线段树单点更新,区间查询。Tree[root]是指在[l,r]距离内比较l大,小于等于r的个数。每次预了解[num[i],n-1]的数码,即要即比num[i]良之再三之个数,再放入num[i],更新。之后,将num[i]转移到尾,比num[i]大的有n

  • 1 – num[i]个,比num[i]小的有num[i]个,移到终极,新增n – 1 –
    num[i]单逆序对,减少num[i]只逆序对。

bet365娱乐场官网 7bet365娱乐场官网 8

 1 #include<iostream>
 2 #include<memory.h>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 5010;
 6 int num[maxn];
 7 int Tree[maxn * 4];//Tree[root]是指在[l,r]区间内比l大,小于等于r的个数
 8 int n;
 9 void Update(int root, int l, int r, int pos)
10 {
11     if (l > pos || r < pos)return;
12     else if (l == r&&l == pos)
13     {
14         Tree[root]++;
15         return;
16     }
17     else
18     {
19         int mid = (l + r) / 2;
20         Update(root * 2 + 1, l, mid, pos);
21         Update(root * 2 + 2, mid + 1, r, pos);
22         Tree[root] = Tree[root * 2 + 1] + Tree[root * 2 + 2];
23     }
24 }
25 int Query(int root, int l, int r, int ll, int rr)
26 {
27     if (r<ll || l>rr) return 0;
28     else if (l >= ll&&r <= rr) return Tree[root];
29     else
30     {
31         int mid = (l + r) / 2;
32         return Query(root * 2 + 1, l, mid, ll, rr) + Query(root * 2 + 2, mid + 1, r, ll, rr);
33     }
34 }
35 int main()
36 {
37     while (~scanf("%d", &n))
38     {
39         memset(Tree, 0, sizeof(Tree));
40         int Sum = 0;
41         for (int i = 0; i < n; i++)
42         {
43             scanf("%d", &num[i]);
44             Sum += Query(0, 0, n - 1, num[i], n - 1);//先询问[num[i],n-1]的数目,即求当前比num[i]大的数的个数
45             Update(0, 0, n - 1, num[i]);//再放入num[i]
46         }
47         int ans = Sum;
48         for (int i = 0; i < n - 1; i++)
49         {
50             Sum += n - 1 - num[i] - num[i];//将num[i]移到后面,比num[i]大的有n - 1 - num[i]个,比num[i]小的有num[i]个,移到最后,新增n - 1 - num[i]个逆序对,减少num[i]个逆序对
51             ans = min(ans, Sum);
52         }
53         printf("%d\n", ans);
54     }
55     return 0;
56 }

View Code

 4、hdu 2795 Billboard(★★★☆☆)

  题意:有一块h*w的告示板,有好多单单位高度、宽度为wi的通告,按输入顺序每次尽量向最好上端、最倚重左摆放,相互之间不可知重叠。求来各个张告示的行数,若无存在,则输出-1.

  思路:线段树单点更新,区间查询。Tree[root]代表第l行及第r行每行最特别剩余可停的最为充分价值,初始设为w,大小也min(h,n)*4.仿照在线处理,每次输入一摆放通告的升幅wi,如果Tree[0]<wi,说明有的行都放不下,否则,如果Tree[mid]不止等于wi,则向左走,否则再于右边走,这样即便能满足每次都尽量提高、向左放。之后持续重复,直到L==R,说明该行是能够放下的无限上一行,然后Tree[root]-=wi,进行翻新。这道题将了解与换代合并起来。

bet365娱乐场官网 9bet365娱乐场官网 10

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int h, w, n;
 5 const int maxn = 200010;
 6 int Tree[maxn * 4];
 7 void Create(int root, int l, int r)
 8 {
 9     if (l == r)
10     {
11         Tree[root] = w;
12         return;
13     }
14     int mid = (l + r) / 2;
15     Create(root * 2 + 1, l, mid);
16     Create(root * 2 + 2, mid + 1, r);
17     Tree[root] = max(Tree[root * 2 + 1], Tree[root * 2 + 2]);
18 }
19 int Query(int root, int l, int r, int v)
20 {
21     if (l == r)
22     {
23         Tree[root] -= v;
24         return l+1;
25     }
26     else
27     {
28         int mid = (l + r) / 2;
29         int ans;
30         if (Tree[root * 2 + 1] >= v) ans=Query(root * 2 + 1, l, mid, v);
31         else ans=Query(root * 2 + 2, mid + 1, r, v);
32         Tree[root] = max(Tree[root * 2 + 1], Tree[root * 2 + 2]);
33         return ans;
34     }
35 }
36 int main()
37 {
38     while (~scanf("%d%d%d", &h, &w, &n))
39     {
40         memset(Tree, 0, sizeof(Tree));
41         if (h > n) h = n;
42         Create(0,0,h - 1);
43         for (int i = 0; i < n; i++)
44         {
45             int len;
46             scanf("%d", &len);
47             if (Tree[0] < len) printf("-1\n");
48             else printf("%d\n", Query(0, 0, h - 1, len));
49         }
50     }
51     return 0;
52 }

View Code

5、hdu 1698 Just a Hook(★★☆☆☆)

  题意:有一个钩子,给起该尺寸。每次能拿中同样段子变为某种金属,不同金属价值不同;对于每次询问,输出区间内的总价值。

  思路:线段树区间更新,区间查询。Tree[root]表示L到R的总价值。PushDown为推创新,此处Tree[root].d记否符,即每次换代时不创新到底,每次区间更新或区间查询时再次展开创新。

bet365娱乐场官网 11bet365娱乐场官网 12

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 const int maxn=100010;
 5 struct Node
 6 {
 7     int sum, d;
 8     Node(int sum0=0,int d0=0):sum(sum0),d(d0){ }
 9 };
10 Node Tree[maxn * 4];
11 int n,q;
12 void PushDown(int root,int l,int r)
13 {
14     if (Tree[root].d)
15     {
16         int mid = (r + l) / 2;
17         Tree[root * 2 + 1].d = Tree[root * 2 + 2].d = Tree[root].d;
18         Tree[root * 2 + 1].sum = Tree[root].d*(mid-l+ 1);
19         Tree[root*2+2].sum= Tree[root].d*(r-mid);
20     }
21     Tree[root].d = 0;
22 }
23 void Create(int root,int l,int r)
24 {
25     if (l == r)
26     {
27         Tree[root].sum = 1;
28         return;
29     }
30     int mid = (l + r) / 2;
31     Create(root * 2 + 1, l, mid);
32     Create(root * 2 + 2, mid + 1, r);
33     Tree[root].sum = Tree[root * 2 + 1].sum + Tree[root * 2 + 2].sum;
34 }
35 void Update(int root, int l, int r, int ll, int rr, int v)
36 {
37     if (r < ll || l>rr)return;
38     else if (l >= ll&&r <= rr)
39     {
40         Tree[root].sum = v*(r - l + 1);
41         Tree[root].d = v;
42         return;
43     }
44     PushDown(root,l,r);
45     int mid = (l + r) / 2;
46     Update(root*2+1, l, mid, ll, rr, v);
47     Update(root*2+2, mid + 1, r, ll, rr, v);
48     Tree[root].sum = Tree[root * 2 + 1].sum + Tree[root * 2 + 2].sum;
49 }
50 int Query(int root, int l, int r, int ll, int rr)
51 {
52     PushDown(root,l,r);
53     if (r< ll || l>rr) return 0;
54     else if (l >= ll&&r <= rr) return Tree[root].sum;
55     else
56     {
57         int mid = (l + r) / 2;
58         return Query(root * 2 + 1, l, mid, ll, rr) + Query(root * 2 + 2, mid + 1, r, ll, rr);
59     }
60 }
61 int main()
62 {
63     int t;
64     int k = 1;
65     scanf("%d", &t);
66     while (t--)
67     {
68         memset(Tree, 0, sizeof(Tree));
69         scanf("%d%d", &n, &q);
70         Create(0, 0, n - 1);
71         for (int i = 0; i < q; i++)
72         {
73             int l,r, v;
74             scanf("%d%d%d", &l, &r, &v);
75             Update(0, 0, n - 1, l-1,r-1, v);
76         }
77         printf("Case %d: The total value of the hook is %d.\n", k,Query(0,0,n-1,0,n-1));
78         k++;
79     }
80     return 0;
81 }

View Code

6、poj3468 A Simple Problem with
Integers(★★☆☆☆)

  题意:给出n个数,每次可挑选一段距离将距离内的数字增长或减去一个价,也得以选取查询同一截距离内的数字之和。

  思路:线段树区间更新,区间查询。

bet365娱乐场官网 13bet365娱乐场官网 14

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 typedef long long LL;
 5 const int maxn = 200100;
 6 struct Node
 7 {
 8     LL sum;
 9     LL d;
10     Node(LL s=0,LL d0=0):sum(s),d(d0){ }
11 }Tree[maxn*4];
12 int n, q;
13 void PushDown(int root, int l, int r)
14 {
15     if (Tree[root].d)
16     {
17         int mid = (l + r) / 2;
18         Tree[root * 2 + 1].d += Tree[root].d;
19         Tree[root * 2 + 2].d += Tree[root].d;
20         Tree[root * 2 + 1].sum += 1ll*Tree[root].d*(mid - l + 1);
21         Tree[root * 2 + 2].sum += 1ll*Tree[root].d*(r - mid);
22     }
23     Tree[root].d = 0;
24 }
25 void PushUp(int root)
26 {
27     Tree[root].sum = Tree[root * 2 + 1].sum + Tree[root * 2 + 2].sum;
28 }
29 void Create(int root, int l, int r)
30 {
31     if (l == r)
32     {
33         scanf("%lld", &Tree[root].sum);
34         return;
35     }
36     int mid = (l + r) / 2;
37     Create(root * 2 + 1, l, mid);
38     Create(root * 2 + 2, mid + 1, r);
39     PushUp(root);
40 }
41 
42 void Update(int root, int l, int r, int ll, int rr, int v)
43 {
44     if (l > rr || r < ll) return;
45     else if (l >= ll&&r <= rr)
46     {
47         Tree[root].sum += 1ll*v*(r - l + 1);
48         Tree[root].d += v;
49         return;
50     }
51     PushDown(root, l, r);
52     int mid = (l + r) / 2;
53     Update(root * 2 + 1, l, mid, ll, rr, v);
54     Update(root * 2 + 2, mid + 1, r, ll, rr, v);
55     PushUp(root);
56 }
57 LL Query(int root, int l, int r, int ll, int rr)
58 {
59     PushDown(root, l, r);
60     if (l > rr || r < ll) return 0;
61     else if (l >= ll&&r <= rr)
62     {
63         return Tree[root].sum;
64     }
65     else
66     {
67         int mid = (l + r) / 2;
68         LL ans = Query(root * 2 + 1, l, mid, ll, rr) + Query(root * 2 + 2, mid + 1, r, ll, rr);
69         PushUp(root);
70         return ans;
71     }
72 }
73 int main()
74 {
75     while (~scanf("%d%d", &n, &q))
76     {
77         memset(Tree, 0, sizeof(Tree));
78         Create(0, 0, n - 1);
79         char c[2];
80         for (int i = 0; i < q; i++)
81         {
82             scanf("%s", c);
83             if (c[0] == 'Q')
84             {
85                 int ll, rr;
86                 scanf("%d%d", &ll, &rr);
87                 printf("%lld\n", Query(0, 0, n - 1, ll - 1, rr - 1));
88             }
89             else
90             {
91                 int ll, rr, v;
92                 scanf("%d%d%d", &ll, &rr, &v);
93                 Update(0, 0, n - 1, ll-1, rr-1, v);
94             }
95         }
96     }
97     return 0;
98 }

View Code

 7、poj2528 Mayor’s posters(★★★★☆)

  题意:给出n张海报的间隔,后来之海报能掩盖掉原来的海报,求最后会看底海报之数码。

  思路:1、由于长的限制很怪,所以待离散化,把装有海报的横职位排个程序(对于非相邻之个别只岗位,需要插入一个在乎两者之间的职,防止离散化后挂出错);2、Tree[root]表示在[l,r]长度区间内所覆盖的海报序号。

bet365娱乐场官网 15bet365娱乐场官网 16

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<algorithm>
  4 using namespace std;
  5 int n, m;
  6 const int maxn = 11111;
  7 int Tree[maxn*2* 4*2];
  8 struct Num
  9 {
 10     int l;
 11     int r;
 12     Num(int ll = 0, int rr = 0) :l(ll), r(rr)
 13     {
 14     }
 15 }num[maxn];
 16 bool vis[maxn];
 17 int Hush[maxn*4];
 18 int cnt = 0;
 19 int PosHush(int v)
 20 {
 21     int l = 0, r = m - 1;
 22     while (l <= r)
 23     {
 24         int mid = (l + r) / 2;
 25         if (Hush[mid] == v) return mid;
 26         else if (Hush[mid] > v) r = mid - 1;
 27         else l = mid + 1;
 28     }
 29     return -1;
 30 }
 31 void PushDown(int root, int l, int r)
 32 {
 33     if (l == r) return;
 34     if (Tree[root])
 35     {
 36         Tree[root * 2 + 1] = Tree[root * 2 + 2] = Tree[root];
 37         Tree[root] = 0;
 38     }
 39 }
 40 void Update(int root, int l, int r, int ll, int rr, int v)
 41 {
 42     PushDown(root, l, r);
 43     if (l > rr || r < ll) return;
 44     else if (ll <= l&&r <= rr)
 45     {
 46         Tree[root] = v;
 47         return;
 48     }
 49     int mid = (l + r) / 2;
 50     Update(root * 2 + 1, l, mid, ll, rr, v);
 51     Update(root * 2 + 2, mid + 1, r, ll, rr, v);
 52 }
 53 
 54 void Query(int root, int l, int r)
 55 {
 56     PushDown(root, l, r);
 57     if (Tree[root])
 58     {
 59         if (!vis[Tree[root]]) cnt++;
 60         vis[Tree[root]] = true;
 61         return;
 62     }
 63     if (l == r) return;
 64     int mid = (l + r) / 2;
 65     Query(root * 2 + 1, l, mid);
 66     Query(root * 2 + 2, mid + 1, r);
 67 }
 68 int main()
 69 {
 70     int t;
 71     scanf("%d", &t);
 72     while (t--)
 73     {
 74         scanf("%d", &n);
 75         m = 0;
 76         for (int i = 0; i < n; i++)
 77         {
 78             scanf("%d%d", &num[i].l, &num[i].r);
 79             Hush[m++] = num[i].l;
 80             Hush[m++] = num[i].r;
 81         }
 82         sort(Hush, Hush + m);
 83         int m2 = 1;
 84         for (int i = 1; i < m; i++)
 85         {
 86             if (Hush[i] != Hush[i - 1]) Hush[m2++] = Hush[i];
 87         }
 88         m = m2;
 89         for (int i = 1; i < m2; i++)
 90         {
 91             if (Hush[i] != Hush[i - 1] + 1) Hush[m++] = Hush[i - 1] + 1;
 92         }
 93         sort(Hush, Hush + m);
 94         memset(Tree, 0, sizeof(Tree));
 95         for (int i = 0; i < n; i++)
 96         {
 97             int ll = PosHush(num[i].l);
 98             int rr = PosHush(num[i].r);
 99             Update(0, 0, m - 1, ll, rr, i + 1);
100         }
101         memset(vis, 0, sizeof(vis));
102         cnt = 0;
103         Query(0, 0, m - 1);
104         printf("%d\n", cnt);
105     }
106     return 0;
107 }

View Code

8、POJ3225 Help with Intervals(★★★★☆)

  题意:原来有一个拖欠集合,每次进行联谊的并、交、对称差、差,最后以升序输出集合中之连区间,若为空则输出set
empty.

  思路:1、区间的开闭:倍增,如果误起l++,如果右开r–;

     2、运算的拍卖:

      U:把区间[l,r]覆盖成1
      I:把[-∞,l)(r,∞]覆盖成0
      D:把区间[l,r]覆盖成0
      C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
      S:[l,r]区间0/1互换

     3、如何创新:

      ①当一个节点得到覆盖标记时把异或标志清空;
      ②设当一个节点得到异或标记的时刻,先判断覆盖标记,如果是0或1,直接改动一下遮盖标记,不然的话改变异或标记。

bet365娱乐场官网 17bet365娱乐场官网 18

  1 #include <cstdio>
  2 #include <iostream>
  3 #include<memory.h>
  4 using namespace std;
  5 const int M = 70000 * 2;
  6 struct segment
  7 {
  8     int tag; //1表示区间所有被覆盖,0表示区间都没有覆盖。-1表示该区间已经更新
  9     bool rev; //异或标记
 10 }tree[M << 2];
 11 void build(int root, int l, int r)
 12 {
 13     tree[root].tag = 0;//初始化
 14     tree[root].rev = false;
 15     if (l == r) return;
 16     int m = (l + r) / 2;
 17     build(root*2+1, l, m);
 18     build(root*2+2, m + 1, r);
 19 }
 20 void pushdown(int root,int l,int r)
 21 {
 22     if (l == r)
 23     {
 24         if (tree[root].rev) //需要翻转的话就翻转
 25         {
 26             tree[root].rev = false;
 27             tree[root].tag ^= 1;
 28         }
 29         return;
 30     }
 31     if (tree[root].tag != -1) //该区间为纯色
 32     {
 33         if (tree[root].rev) tree[root].tag ^= 1;
 34         tree[root*2+1].tag = tree[root*2+2].tag = tree[root].tag;
 35         tree[root].tag = -1;//已经下放
 36         tree[root*2+1].rev = tree[root*2+2].rev = tree[root].rev = false;
 37     }
 38     if (tree[root].rev)//需要异或
 39     {
 40         tree[root].rev = false;
 41         if (tree[root*2+1].tag == -1)
 42             tree[root*2+1].rev ^= 1;//下放
 43         else tree[root*2+1].tag ^= 1;//否则直接标记该区间整个是否覆盖
 44         if (tree[root*2+2].tag == -1)
 45             tree[root*2+2].rev ^= 1;
 46         else tree[root*2+2].tag ^= 1;
 47     }
 48 }
 49 void update(int root,int l,int r,int ll, int rr, int v)
 50 {
 51     if (l > rr || r < ll)return;
 52     if (l >= ll&&r <= rr)
 53     {
 54         if (v<2) //赋值操作
 55         {
 56             tree[root].rev = false;
 57             tree[root].tag = v;
 58         }
 59         else //翻转操作
 60         {
 61             if (tree[root].tag != -1) //区间为纯色,直接翻转即可
 62                 tree[root].tag ^= 1;
 63             else tree[root].rev ^= 1; //异或
 64         }
 65         return;
 66     }
 67     int m = (l + r) / 2;
 68     pushdown(root,l,r);//向下更新子树
 69     if (rr <= m) update(root*2+1, l, m,ll,rr, v);
 70     else if (ll>m) update(root*2+2, m+1, r,ll,rr, v);
 71     else
 72     {
 73         update(root*2+1, l, m,ll,rr, v);
 74         update(root*2+2, m + 1, r,ll,rr, v);
 75     }
 76 }
 77 bool vis[M];
 78 void Query(int root,int l,int r)
 79 {
 80     
 81     if (tree[root].tag != -1)
 82     {
 83         if (tree[root].tag == 1)
 84             for (int i = l; i <= r; i++)
 85                 vis[i] = true;
 86         return;
 87     }
 88     pushdown(root,l,r);
 89     int mid=(l + r)/2;
 90     Query(root*2+1,l,mid);
 91     Query(root*2+2,mid+1,r);
 92 }
 93 int main()
 94 {
 95     //freopen("in.txt", "r", stdin);
 96     build(0, 0, M);
 97     int l, r;
 98     char op, a, b;
 99     while (scanf("%c %c%d,%d%c", &op, &a, &l, &r, &b) != -1)
100     {
101         getchar();//读入换行符
102         l <<= 1; if (a == '(') l++;//开闭区间处理
103         r <<= 1; if (b == ')') r--;
104         switch (op)
105         {
106         case 'U':update(0,0,M, l, r, 1); break;
107         case 'I':update(0,0,M, 0, l - 1, 0); update(0, 0, M, r + 1, M, 0); break;
108         case 'D':update(0, 0, M, l, r, 0); break;
109         case 'C':update(0, 0, M, 0, l - 1, 0); 
110             update(0, 0, M, r + 1, M, 0); 
111             update(0, 0, M, l, r, 2); 
112             break;
113         case 'S':update(0, 0, M, l, r, 2);
114         }
115     }
116     memset(vis, 0, sizeof(vis));
117     Query(0, 0, M);
118     bool flag = true;
119     for (int i = 0; i<M; i++)
120     {
121         if (!vis[i]) continue;
122         flag = false;
123         int start = i, end;
124         while (vis[i] && i<M) i++;
125         printf("%c%d,%d%c ", start & 1 ? '(' : '[', start / 2, i / 2, (i - 1) & 1 ? ')' : ']');
126     }
127     if (flag) puts("empty set");
128     else printf("\n");
129     return 0;
130 }

View Code

 9、ZOJ 1610 Count the Colors

  题意:对于同一块区域染色,求最后能够来看的颜料。用颜色编号+颜色块输出。(输入时涂色的间距为左端点及右手端点,即只要个别对[2,3],[4,5]上相同的颜料,由于3同4里面还有平等段子空,所以是鲜单颜色块。这种情景下,区间更新时好选取将R-1,对答案没有影响)

  思路:线段树区间染色问题。

bet365娱乐场官网 19bet365娱乐场官网 20

 1 #include<iostream>
 2 #include<memory.h>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 const int maxn = 8010;
 7 int tree[maxn << 2];
 8 int n;
 9 int tg[maxn];
10 int cnt[maxn];
11 void PushDown(int root,int l,int r)
12 {
13     if (tree[root]!= -1)
14     {
15         tree[root * 2 + 1]= tree[root * 2 + 2]= tree[root];
16         tree[root] = -1;
17     }
18 }
19 void Update(int root, int l, int r, int ll, int rr, int color)
20 {
21     if (l > rr || r < ll) return;
22     if (ll <= l&&r <= rr)
23     {
24         tree[root] = color;
25         return;
26     }
27     PushDown(root,l,r);
28     int mid = (l + r) / 2;
29     Update(root * 2 + 1, l, mid, ll, rr, color);
30     Update(root * 2 + 2, mid + 1, r, ll, rr, color);
31     if (tree[root * 2 + 1]== tree[root * 2 + 2]&& tree[root * 2 + 1]!=-1) tree[root] = tree[root * 2 + 1];
32     else tree[root] = -1;
33 }
34 void Query(int root, int l, int r)
35 {
36     //PushDown(root,l,r);
37     if (tree[root] != -1)
38     {
39         for (int i = l; i <= r; i++)
40         {
41             tg[i] = tree[root];
42         }
43         return;
44     }
45     if (l == r)return;
46     int mid = (l + r) / 2;
47     Query(root * 2 + 1, l, mid);
48     Query(root * 2 + 2, mid + 1, r);
49 }
50 int main()
51 {
52     while (~scanf("%d", &n))
53     {
54         memset(tree, -1, sizeof(tree));
55         memset(tg, -1, sizeof(tg));
56         for (int i = 0; i < n; i++)
57         {
58             int l, r, color;
59             scanf("%d%d%d", &l, &r, &color);
60             Update(0, 0, maxn, l, r-1, color);//输入涂色范围为端点,建立时涂色范围改为区域
61         }
62         Query(0, 0, maxn);
63         memset(cnt, 0, sizeof(cnt));
64         for (int i = 1; i < maxn; i++)
65         {
66             if (tg[i] != tg[i - 1])
67             {
68                 if (tg[i - 1] != -1)
69                 {
70                     cnt[tg[i - 1]]++;
71                 }
72             }
73         }
74         for (int i = 0; i < maxn; i++)
75         {
76             if (cnt[i]) printf("%d %d\n", i, cnt[i]);
77         }
78         printf("\n");
79     }
80     return 0;
81 }

View Code

10、hdu 4027 Can you answer these
queries

  题意:对于一个数组,每次挑一个区间将该中间的因素还置为原先元素的平方根(向下取整),或了解同段距离的和。

  思路:线段树单点更新(由于每个数还无自然同,需要对区间内的每个数进行单独开方),区间查询。每次换代区间时,先进行相同不行询问,如果距离内元素还也1,则无需在开展更新。

bet365娱乐场官网 21bet365娱乐场官网 22

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 const int maxn = 100100;
 5 long long tree[maxn*4];
 6 int n,m;
 7 void Build(int root, int l, int r)
 8 {
 9     if (l == r)
10     {
11         scanf("%lld", &tree[root]);
12         return;
13     }
14     int mid = (l + r) / 2;
15     Build(root * 2 + 1, l, mid);
16     Build(root * 2 + 2, mid + 1, r);
17     tree[root] = tree[root * 2 + 1] + tree[root * 2 + 2];
18 }
19 void Update(int root, int l, int r, int ll, int rr)
20 {
21     if (l > rr || r < ll) return;
22     if (l >= ll&&r <= rr&&l == r)
23     {
24         if (tree[root] > 1) tree[root] = (long long)sqrt(1.0*tree[root]);
25         return;
26     }
27     int mid = (l + r) / 2;
28     Update(root * 2 + 1, l, mid, ll, rr);
29     Update(root * 2 + 2, mid + 1,r, ll, rr);
30     tree[root] = tree[root * 2 + 1] + tree[root * 2 + 2];
31 }
32 long long Query(int root, int l, int r, int ll, int rr)
33 {
34     if (l > rr || r < ll)return 0;
35     if (l >= ll&&r <= rr)return tree[root];
36     int mid = (l + r) / 2;
37     return Query(root * 2 + 1, l, mid, ll, rr) + Query(root * 2 + 2, mid + 1, r, ll, rr);
38 }
39 int main()
40 {
41     int Case = 1;
42     while (~scanf("%d",&n))
43     {
44         printf("Case #%d:\n", Case++);
45         Build(0, 0, n - 1);
46         scanf("%d", &m);
47         for (int i = 0; i < m; i++)
48         {
49             int t, x, y;
50             scanf("%d%d%d", &t, &x, &y);
51             if (x > y)
52             {
53                 int t = x;
54                 x = y;
55                 y = t;
56             }
57             if (t == 0)
58             {
59                 if (Query(0, 0, n - 1, x - 1, y - 1) != y - x + 1)//判断一下是否需要继续更新
60                     Update(0, 0, n - 1, x - 1, y - 1);
61             }
62             else printf("%lld\n", Query(0, 0, n - 1, x - 1, y - 1));
63         }
64         printf("\n");
65     }
66     return 0;
67 }

View Code

11、hdu 1540 Tunnel Warfare

  题意:每次可选择破坏一个聚落,或修复最近坏的一个山村,或询问有村庄所于的接连区间(该距离内村并未叫磨损)的尺寸。

  思路:线段树单点更新,区间查询。在线段树里维护[l,r]内左边最丰富连区间长度和右手最丰富连区间长度。

bet365娱乐场官网 23bet365娱乐场官网 24

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <math.h>
  5 #include <stdlib.h>
  6 using namespace std;
  7 
  8 const int maxn = 50000 + 10;
  9 
 10 int n, m;
 11 int s[maxn], top;//s为模拟栈
 12 //区间合并
 13 struct node
 14 {
 15     int l, r;
 16     int ls, rs, ms;//ls,左端最大连续区间,rs右端最大连续区间,ms整个区间内的最大连续长度
 17 } a[maxn << 2];
 18 
 19 void init(int l, int r, int root)
 20 {
 21     a[root].l = l;
 22     a[root].r = r;
 23     a[root].ls = a[root].rs = a[root].ms = r - l + 1;
 24     if (l != r)
 25     {
 26         int mid = (l + r) >> 1;
 27         init(l, mid, root * 2);
 28         init(mid + 1, r, 2 * root + 1);
 29     }
 30 }
 31 
 32 void insert(int root, int t, int x)
 33 {
 34     if (a[root].l == a[root].r)
 35     {
 36         if (x == 1)
 37             a[root].ls = a[root].rs = a[root].ms = 1;//修复
 38         else
 39             a[root].ls = a[root].rs = a[root].ms = 0;//破坏
 40         return;
 41     }
 42     int mid = (a[root].l + a[root].r) >> 1;
 43     if (t <= mid)
 44         insert(2 * root, t, x);
 45     else
 46         insert(2 * root + 1, t, x);
 47     a[root].ls = a[2 * root].ls;//左区间
 48     a[root].rs = a[2 * root + 1].rs;//右区间
 49     a[root].ms = max(max(a[2 * root].ms, a[2 * root + 1].ms), a[2 * root].rs + a[2 * root + 1].ls);//父亲区间内的最大区间必定是,左子树最大区间,右子树最大区间,左右子树合并的中间区间,三者中最大的区间值
 50     if (a[2 * root].ls == a[2 * root].r - a[2 * root].l + 1)//左子树区间满了的话,父亲左区间要加上右孩子的左区间
 51         a[root].ls += a[2 * root + 1].ls;
 52     if (a[2 * root + 1].rs == a[2 * root + 1].r - a[2 * root + 1].l + 1)//同理
 53         a[root].rs += a[2 * root].rs;
 54 }
 55 
 56 int query(int root, int t)
 57 {
 58     if (a[root].l == a[root].r || a[root].ms == 0 || a[root].ms == a[root].r - a[root].l + 1)//到了叶子节点或者该访问区间为空或者已满都不必要往下走了
 59         return a[root].ms;
 60     int mid = (a[root].l + a[root].r) >> 1;
 61     if (t <= mid)
 62     {
 63         if (t >= a[2 * root].r - a[2 * root].rs + 1)//判断当前这个数是否在左区间的右连续中,因为t<=mid,看左子树,a[2*i].r-a[2*i].rs+1代表左子树右边连续区间的左边界值,如果t在左子树的右区间内,则要看右子树的左区间有多长并返回
 64             return query(2 * root, t) + query(2 * root + 1, mid + 1);
 65         else
 66             return query(2 * root, t);//如果不在左子树的右边界区间内,则只需要看左子树
 67     }
 68     else
 69     {
 70         if (t <= a[2 * root + 1].l + a[2 * root + 1].ls - 1)//同理
 71             return query(2 * root + 1, t) + query(2 * root, mid);
 72         else
 73             return query(2 * root + 1, t);
 74     }
 75 }
 76 
 77 int main()
 78 {
 79     int i, j, x;
 80     char ch[2];
 81     while (~scanf("%d%d", &n, &m))
 82     {
 83         top = 0;
 84         init(1, n, 1);
 85         while (m--)
 86         {
 87             scanf("%s", ch);
 88             if (ch[0] == 'D')
 89             {
 90                 scanf("%d", &x);
 91                 s[top++] = x;
 92                 insert(1, x, 0);
 93             }
 94             else if (ch[0] == 'Q')
 95             {
 96                 scanf("%d", &x);
 97                 printf("%d\n", query(1, x));
 98             }
 99             else
100             {
101                 if (x>0)
102                 {
103                     x = s[--top];
104                     insert(1, x, 1);
105                 }
106             }
107         }
108     }
109     return 0;
110 }

View Code

12、hdu 3974  Assign the task

  题意:给出一个职工及其直属上司。每次可拿某项任务交给一个主持,他随同下属的做事都见面进展该项工作,或询问有人现在当拓展什么任务。

  思路:线段树区间更新、单点查询。首先对员工及上级之间的关系可建立平等棵树,通过自树根DFS把持有职工还编号,同时记录有个体及其属下的数码区间。

bet365娱乐场官网 25bet365娱乐场官网 26

  1 ##include<stdio.h>
  2 #include<algorithm>
  3 #include<vector>
  4 using namespace std;
  5 
  6 const int MAXN = 50005;
  7 
  8 int Start[MAXN], End[MAXN];//每个员工所有下属的开始和结束节点,包含本身
  9 int index;//DFS用记录节点的编号
 10 vector<int> G[MAXN];//保存边
 11 
 12 void DFS(int k)
 13 {
 14     Start[k] = ++index;
 15     for (int i = 0, len = G[k].size(); i<len; i++)
 16         DFS(G[k][i]);
 17     End[k] = index;
 18 }
 19 
 20 struct SegmentTree
 21 {
 22     int L, R, task;
 23     bool isCover;
 24     int Mid()
 25     {
 26         return (L + R) / 2;
 27     }
 28 }a[MAXN * 4];
 29 
 30 void BuildTree(int r, int L, int R)
 31 {
 32     a[r].L = L, a[r].R = R;
 33     a[r].task = -1, a[r].isCover = false;//初始化
 34 
 35     if (L == R)return;
 36 
 37     BuildTree(r << 1, L, a[r].Mid());
 38     BuildTree(r << 1 | 1, a[r].Mid() + 1, R);
 39 }
 40 void Down(int r)
 41 {//延迟更新
 42     if (a[r].L != a[r].R && a[r].isCover)
 43     {
 44         a[r << 1].isCover = a[r << 1 | 1].isCover = true;
 45         a[r << 1].task = a[r << 1 | 1].task = a[r].task;
 46         a[r].isCover = false;
 47     }
 48 }
 49 void Insert(int r, int L, int R, int task)
 50 {
 51     Down(r);
 52 
 53     if (a[r].L == L && a[r].R == R)
 54     {
 55         a[r].isCover = true;
 56         a[r].task = task;
 57         return;
 58     }
 59 
 60     if (R <= a[r].Mid())
 61         Insert(r << 1, L, R, task);
 62     else if (L > a[r].Mid())
 63         Insert(r << 1 | 1, L, R, task);
 64     else
 65     {
 66         Insert(r << 1, L, a[r].Mid(), task);
 67         Insert(r << 1 | 1, a[r].Mid() + 1, R, task);
 68     }
 69 }
 70 int  Query(int r, int k)
 71 {
 72     Down(r);
 73 
 74     if (a[r].L == a[r].R)
 75         return a[r].task;
 76 
 77     if (k <= a[r].Mid())
 78         return Query(r << 1, k);
 79     else
 80         return Query(r << 1 | 1, k);
 81 }
 82 
 83 int main()
 84 {
 85     int T, t = 1;
 86 
 87     scanf("%d", &T);
 88 
 89     while (T--)
 90     {
 91         int i, N, M, u, v; char s[10];
 92 
 93         scanf("%d", &N);
 94 
 95         for (i = 1; i <= N; i++)
 96             G[i].clear();
 97         bool use[MAXN] = { 0 };
 98         for (i = 1; i<N; i++)
 99         {
100             scanf("%d%d", &u, &v);//v是u的直属上司
101             G[v].push_back(u);
102             use[u] = true;//表明下属
103         }
104 
105         index = 0;
106         for (i = 1; i <= N; i++)if (!use[i])//总boss
107         {
108             DFS(i); break;
109         }
110 
111         BuildTree(1, 1, N);
112         printf("Case #%d:\n", t++);
113 
114         scanf("%d", &M);
115 
116         while (M--)
117         {
118             scanf("%s", s);
119 
120             if (s[0] == 'C')
121             {
122                 scanf("%d", &u);
123                 printf("%d\n", Query(1, Start[u]));
124             }
125             else
126             {
127                 scanf("%d%d", &u, &v);
128                 Insert(1, Start[u], End[u], v);
129             }
130         }
131     }
132     return 0;
133 }

View Code

13、HDU 1255
覆盖的面积(矩形面积并)

  题意:给有若干单矩形的左上坐标和右边下坐标,询问有矩形覆盖两糟糕以及以上的面积以及。

  思路:对于每个矩形的左手边与右手边立线段,同时记录下有出现过的y坐标,然后照y坐标从小到不行排序并作距离建立线段树,每次按照线段的x值从小到好插入线段树。

bet365娱乐场官网 27bet365娱乐场官网 28

  1 #include<iostream>
  2 #include<string>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 #include<map>
  7 #include<cmath>
  8 #include<stack>
  9 #include<set>
 10 #include<vector>
 11 #include<algorithm>
 12 #define LL long long
 13 #define inf 1<<30//极大值
 14 using namespace std;
 15 const int N = 2005;
 16 int n;
 17 double y[N];
 18 struct LINE
 19 {
 20     double x;//竖线的横坐标
 21     double y_down, y_up;//竖线的上下端点的y坐标
 22     int flag;//矩形左侧还是右侧
 23 }line[N];
 24 struct node
 25 {
 26     double l, r;
 27     double x;
 28     int cover;
 29     bool flag;
 30 }node[N << 2];
 31 bool cmp(LINE a, LINE b)
 32 {
 33     return a.x<b.x;
 34 }
 35 void build(int rt, int l, int r)
 36 {
 37     node[rt].l = y[l];
 38     node[rt].r = y[r];
 39     node[rt].x = -1;
 40     node[rt].flag = false;
 41     node[rt].cover = 0;
 42     if (l + 1 == r)
 43     {
 44         node[rt].flag = true;//叶子结点
 45         return;
 46     }
 47     int mid = (l + r) >> 1;
 48     build(rt << 1, l, mid);
 49     build(rt << 1 | 1, mid, r);
 50 }
 51 double Insert_query(int rt, double x, double l, double r, int flag)
 52 {
 53     if (l >= node[rt].r || r <= node[rt].l) return 0;
 54     if (node[rt].flag)//叶子结点,只有到最小区间更新
 55     {
 56         if (node[rt].cover>1)//超过1次
 57         {
 58             double pre = node[rt].x;
 59             double ans = (x - pre)*(node[rt].r - node[rt].l);
 60             node[rt].x = x;
 61             node[rt].cover += flag;
 62             return ans;
 63         }
 64         else
 65         {
 66             node[rt].x = x;
 67             node[rt].cover += flag;
 68             return 0;
 69         }
 70     }
 71     double ans1, ans2;
 72     ans1 = Insert_query(rt << 1, x, l, r, flag);
 73     ans2 = Insert_query(rt << 1 | 1, x, l, r, flag);
 74     return ans1 + ans2;
 75 }
 76 int main()
 77 {
 78     int t;
 79     double x1, x2, y1, y2;
 80     scanf("%d", &t);
 81     while (t--)
 82     {
 83         scanf("%d", &n);
 84         int cnt = -1;
 85         for (int i = 0; i<n; i++)
 86         {
 87             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
 88             y[++cnt] = y1;
 89             line[cnt].x = x1;
 90             line[cnt].y_down = y1;
 91             line[cnt].y_up = y2;
 92             line[cnt].flag = 1;//矩形左边
 93             y[++cnt] = y2;
 94             line[cnt].x = x2;
 95             line[cnt].y_down = y1;
 96             line[cnt].y_up = y2;
 97             line[cnt].flag = -1;//矩形右边
 98         }
 99         sort(y, y + cnt + 1);//把所有y坐标(横线)按y从小到大排列
100         sort(line, line + cnt + 1, cmp);//把所有竖线按x从小到大排列
101         build(1, 0, cnt);
102         double area = 0;
103         for (int i = 0; i <= cnt; i++)
104         {
105             area += Insert_query(1, line[i].x, line[i].y_down, line[i].y_up, line[i].flag);
106         }
107         printf("%.2lf\n", area);
108     }
109     return 0;
110 }

View Code

 14、uva 11235/poj 3368/hdu 1806
 Frequent values

  题意:给闹一个非递减序列,求[l,r]中间的数的无限深出现次数。

  思路:将平之值的高频划分也1单片,把每个片号码建立线段树。

bet365娱乐场官网 29bet365娱乐场官网 30

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 100005;
 5 const int maxv = 100005;
 6 int tree[maxn*4], left[maxn], right[maxn], num[maxn],id[maxv*2];
 7 
 8 void PushUp(int rt)
 9 {
10     tree[rt] = max(tree[rt*2+1], tree[rt*2+2]);
11 }
12 
13 void build(int root,int l,int r)
14 {
15     if (l == r)
16     {
17         tree[root] = right[l] - left[l] + 1;
18         return;
19     }
20     int mid = (l + r)/2;
21     build(root*2+1,l,mid);
22     build(root*2+2,mid+1,r);
23     PushUp(root);
24 }
25 
26 int Query(int root,int l,int r,int ql,int qr)
27 {
28     if (r<ql || l>qr) return 0;
29     if (ql <= l && r <= qr)
30     {
31         return tree[root];
32     }
33     int mid = (l + r)/2;
34     return max(Query(root * 2 + 1, l, mid, ql, qr), Query(root * 2 + 2, mid + 1, r, ql, qr));
35 }
36 
37 int main()
38 {
39     int n, q;
40     while (~scanf("%d%d", &n, &q))
41     {
42         if (n == 0) break;
43         for (int i = 1; i <= n;i++)
44         {
45             scanf("%d", &num[i]);
46             num[i] += 100000;
47         }
48         int cnt = 0;
49         for (int i = 1; i <= n; i++)
50         {
51             int v = num[i],j=i;
52             while (j + 1 <= n&&num[j + 1] == v) j++;
53             left[cnt] = i;
54             right[cnt] = j;
55             id[v] = cnt;
56             i = j;
57             cnt++;
58         }
59         build(0,0,cnt-1);
60         while (q--)
61         {
62             int a, b;
63             scanf("%d%d", &a, &b);
64             int ida = id[num[a]], idb=id[num[b]];
65             if (idb == ida) printf("%d\n", b - a + 1);
66             else if (idb == ida + 1) printf("%d\n", max(right[ida] - a + 1, b - left[idb] + 1));
67             else printf("%d\n", max(max(right[ida] - a + 1, b - left[idb] + 1), Query(0,0,cnt-1,ida+1,idb-1)));
68         }
69     }
70     return 0;
71 }

View Code

 15、LA 3938 Ray, Pass me the
dishes!

  题意:给出一个数列,求[l,r]距离中极度酷连续子区间和,并吃闹无限小之子区间范围。

  思路:关键在pushup.

bet365娱乐场官网 31bet365娱乐场官网 32

  1 #include <cstdio>  
  2 #include <iostream>  
  3 #include <algorithm>  
  4 using namespace std;
  5 const int maxn = 500100;
  6 int lr[maxn << 2], rl[maxn << 2], sr[maxn << 2], sl[maxn << 2];
  7 //lr[]为区间前缀和的末位置,rl[]为区间后缀和的首位置,sr[]、sl[]为区间最大连续和的首尾位置
  8 long long maxl[maxn << 2], maxm[maxn << 2], maxr[maxn << 2];
  9 //maxl[]为最大前缀和,maxm为最大连续子区间和,maxr为最大后缀和
 10 long long c[maxn];
 11 //c[i]为输入数组的前缀和
 12 struct node
 13 {
 14     int x, y, lr, rl;
 15     long long sum, maxl, maxr;
 16 };
 17 
 18 long long Max(long long a, long long b, long long c)
 19 {
 20     return max(a, max(b, c));
 21 }
 22 
 23 void PushUp(int root,int l, int r)
 24 {
 25     int mid = (l + r)/2;
 26     //处理根区间最大前缀和
 27     if (maxl[root*2+1] + c[mid] - c[l - 1] <= maxl[root*2])
 28     {//如果【左区间最大前缀和】大于等于【左区间和+右区间最大前缀和】
 29         maxl[root] = maxl[root*2];
 30         lr[root] = lr[root*2];
 31     }
 32     else
 33     {
 34         maxl[root] = maxl[root*2+1] + c[mid] - c[l - 1];
 35         lr[root] = lr[root*2+1];
 36     }
 37     //处理根区间最大后缀和
 38     if (maxr[root << 1] + c[r] - c[mid] < maxr[root << 1 | 1])
 39     {//如果【右区间最大后缀和】大于【左区间最大后缀和+右区间和】
 40         maxr[root] = maxr[root*2+1];
 41         rl[root] = rl[root*2+1];
 42     }
 43     else
 44     {
 45         maxr[root] = maxr[root*2] + c[r] - c[mid];
 46         rl[root] = rl[root*2];
 47     }
 48     //处理根区间最大子区间和
 49     if (maxm[root*2] >= maxm[root*2+1])
 50     {//如果【左区间最大子区间连续和】大于等于【右区间最大子区间连续和】
 51         maxm[root] = maxm[root*2], sl[root] = sl[root*2], sr[root] = sr[root*2];
 52     }
 53     else
 54     {
 55         maxm[root] = maxm[root*2+1], sl[root] = sl[root*2+1], sr[root] = sr[root*2+1];
 56     }
 57     if (maxm[root] < maxr[root*2] + maxl[root*2+1] || (maxm[root] == maxr[root*2] + maxl[root*2+1] && (rl[root *2] < sl[root] || (rl[root*2] == sl[root] && lr[root*2+1] <= sr[root]))))
 58     {//如果(【左区间最大后缀和】+【右区间最大前缀和】大于【根最大子区间连续和】)或者两者相等但是区间范围前者小
 59         maxm[root] = maxr[root*2] + maxl[root*2+1];
 60         sl[root] = rl[root*2];
 61         sr[root] = lr[root*2+1];
 62     }
 63 }
 64 
 65 node query(int root, int l, int r,int ql, int qr)
 66 {
 67     node res;
 68     if (ql <= l && qr >= r)
 69     {
 70         res.x = sl[root];
 71         res.y = sr[root];
 72         res.lr = lr[root];
 73         res.rl = rl[root];
 74         res.maxl = maxl[root];
 75         res.maxr = maxr[root];
 76         res.sum = maxm[root];
 77         return res;
 78     }
 79     int mid= (l + r)/2;
 80     if (qr <= mid) return query(root*2,l,mid,ql,qr);
 81     else if (ql > mid) return query(root*2+1,mid+1,r,ql,qr);
 82     else
 83     {
 84         node a, b;
 85         a = query(root * 2, l, mid, ql, qr);
 86         b = query(root * 2 + 1, mid + 1, r, ql, qr);
 87         //相当于node类型的pushup
 88         if (b.maxl + c[mid] - c[l - 1] <= a.maxl)
 89         {
 90             res.maxl = a.maxl;
 91             res.lr = a.lr;
 92         }
 93         else
 94         {
 95             res.maxl = b.maxl + c[mid] - c[l - 1];
 96             res.lr = b.lr;
 97         }
 98         if (a.maxr + c[r] - c[mid] < b.maxr)
 99         {
100             res.maxr = b.maxr;
101             res.rl = b.rl;
102         }
103         else
104         {
105             res.maxr = a.maxr + c[r] - c[mid];
106             res.rl = a.rl;
107         }
108         if (a.sum >= b.sum)
109         {
110             res.sum = a.sum, res.x = a.x, res.y = a.y;
111         }
112         else
113         {
114             res.sum = b.sum, res.x = b.x, res.y = b.y;
115         }
116         if (res.sum < a.maxr + b.maxl || (res.sum == a.maxr + b.maxl && (res.x > a.rl || (res.x == a.rl && res.y > b.lr))))
117         {
118             res.sum = a.maxr + b.maxl;
119             res.x = a.rl;
120             res.y = b.lr;
121         }
122         return res;
123     }
124 }
125 
126 void Build(int root,int l,int r)
127 {
128     if (l == r)
129     {
130         sl[root] = lr[root] = rl[root] = sr[root] = l;
131         maxl[root] = maxr[root] = maxm[root] = c[l] - c[l - 1];
132         return;
133     }
134     int mid = (l + r) >> 1;
135     Build(root*2,l,mid);
136     Build(root*2+1,mid+1,r);
137     PushUp(root,l, r);
138 }
139 
140 int main()
141 {
142     int Case = 1, n, m;
143     while (~scanf("%d%d", &n, &m))
144     {
145         c[0] = 0;
146         for (int i = 1; i <= n; i++)
147         {
148             scanf("%lld", &c[i]);
149             c[i] += c[i - 1];
150         }
151         Build(1,1,n);
152         printf("Case %d:\n", Case++);
153         while (m--)
154         {
155             int a, b;
156             scanf("%d%d", &a, &b);
157             node ans = query(1,1,n,a, b);
158             printf("%d %d\n", ans.x, ans.y);
159         }
160     }
161     return 0;
162 }

View Code

 16、UVA 11992 Fast Matrix
Operations

  题意:给出一个矩阵,每次可add或set指定的子矩阵,或者了解一个子矩阵的跟、最深价值、最小价。

  思路:由于行数不跳20,直接建r*c*4尺寸的线树,每次对矩阵操作时分别针对各国一行操作。更新时只顾先set后add.

bet365娱乐场官网 33bet365娱乐场官网 34

  1 #include<iostream>
  2 #include<algorithm>
  3 using namespace std;
  4 const int maxn = 1000100;
  5 const int INF = 0x7fffffff;
  6 struct node
  7 {
  8     int maxv, minv, sumv;
  9     int setv, addv;
 10     node(int mx=0,int mn=0,int sm=0,int st=-1,int ad=0):maxv(mx),minv(mn),sumv(sm),setv(st),addv(ad){ }
 11 }tree[maxn<<2];
 12 void Setv(int root,int l,int r, int v)
 13 {
 14     tree[root].addv = 0;
 15     tree[root].setv = v;
 16     tree[root].sumv = (r - l + 1)*v;
 17     tree[root].maxv = v;
 18     tree[root].minv = v;
 19 }
 20 void Addv(int root, int l, int r, int v)
 21 {
 22     tree[root].addv += v;
 23     tree[root].sumv += (r - l + 1)*v;
 24     tree[root].maxv += v;
 25     tree[root].minv += v;
 26 }
 27 void PushDown(int root, int l, int r)
 28 {
 29     int mid = (l + r) / 2;
 30     if (tree[root].setv >= 0)
 31     {
 32         Setv(root * 2, l, mid, tree[root].setv);
 33         Setv(root * 2+1, mid+1,r, tree[root].setv);
 34         tree[root].setv = -1;
 35     }
 36     if (tree[root].addv > 0)
 37     {
 38         Addv(root * 2, l, mid, tree[root].addv);
 39         Addv(root * 2 + 1, mid + 1, r, tree[root].addv);
 40         tree[root].addv = 0;
 41     }
 42 }
 43 void PushUp(int root, int l, int r)
 44 {
 45     tree[root].sumv = tree[root * 2].sumv + tree[root * 2 + 1].sumv;
 46     tree[root].maxv = max(tree[root * 2].maxv, tree[root * 2 + 1].maxv);
 47     tree[root].minv = min(tree[root * 2].minv, tree[root * 2 + 1].minv);
 48     tree[root].setv = -1, tree[root].addv = 0;
 49 }
 50 void Build(int root, int l, int r)
 51 {
 52     if (l == r)
 53     {
 54         tree[root] = node(0, 0, 0, -1, 0);
 55         return;
 56     }
 57     int mid = (l + r) / 2;
 58     Build(root * 2, l, mid);
 59     Build(root * 2 + 1, mid + 1, r);
 60     PushUp(root, l, r);
 61 }
 62 void Update(int root, int l, int r, int ul, int ur,int v, int flag)
 63 {//flag=1,add;flag=2,set
 64     if (l > ur || r < ul) return;
 65     if (ul <= l&&r <= ur)
 66     {
 67         if (flag == 1) Addv(root, l, r, v);
 68         else Setv(root, l, r, v);
 69         return;
 70     }
 71     PushDown(root, l, r);
 72     int mid = (l + r) / 2;
 73     Update(root * 2, l, mid, ul, ur, v, flag);
 74     Update(root * 2 + 1, mid + 1, r, ul, ur, v, flag);
 75     PushUp(root, l, r);
 76 }
 77 node Query(int root, int l, int r, int ql, int qr)
 78 {
 79     if (l > qr || r < ql) return node(-INF,INF,0,-1,0);
 80     if (ql <= l&&r <= qr) return tree[root];
 81     PushDown(root, l, r);
 82     int mid = (l + r) / 2;
 83     node n1 = Query(root * 2, l, mid, ql, qr);
 84     node n2 = Query(root * 2 + 1, mid + 1, r, ql, qr);
 85     return node(max(n1.maxv, n2.maxv), min(n1.minv, n2.minv), n1.sumv + n2.sumv);
 86 }
 87 int main()
 88 {
 89     int r, c, q;
 90     while (~scanf("%d%d%d", &r, &c, &q))
 91     {
 92         Build(1, 1, r*c);
 93         while (q--)
 94         {
 95             int sign;
 96             scanf("%d", &sign);
 97             if (sign != 3)
 98             {
 99                 int x1, x2, y1, y2, v;
100                 scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);
101                 for (int i = x1 - 1; i < x2; i++)
102                 {
103                     Update(1, 1, r*c, i*c + y1, i*c + y2, v, sign);
104                 }
105             }
106             else
107             {
108                 node ans(-INF,INF,0);
109                 int x1, x2, y1, y2;
110                 scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
111                 for (int i = x1 - 1; i < x2; i++)
112                 {
113                     node tmp = Query(1, 1, r*c, i*c + y1, i*c + y2);
114                     ans.maxv = max(ans.maxv, tmp.maxv);
115                     ans.minv = min(ans.minv, tmp.minv);
116                     ans.sumv += tmp.sumv;
117                 }
118                 printf("%d %d %d\n", ans.sumv, ans.minv, ans.maxv);
119             }
120         }
121     }
122     return 0;
123 }

View Code

 17、LA 2191 Potentiometers

  题意:有多少个串联的电阻,每次可创新一个电阻的阻值或了解同段距离内的电阻。

  思路:简单线段树。单点更新,区间查询。

bet365娱乐场官网 35bet365娱乐场官网 36

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 200010;
 5 int tree[maxn << 2];
 6 char s[10];
 7 void Build(int root, int l, int r)
 8 {
 9     if (l == r)
10     {
11         scanf("%d", &tree[root]);
12         return;
13     }
14     int mid = (l + r) / 2;
15     Build(root * 2, l, mid);
16     Build(root * 2 + 1, mid + 1, r);
17     tree[root] = tree[root * 2] + tree[root * 2 + 1];
18 }
19 void Update(int root, int l, int r, int pos, int v)
20 {
21     if (pos<l || pos>r) return;
22     if (pos == l&&pos == r)
23     {
24         tree[root] = v;
25         return;
26     }
27     int mid = (l + r) / 2;
28     Update(root * 2, l, mid, pos, v);
29     Update(root * 2 + 1, mid + 1, r, pos, v);
30     tree[root] = tree[root * 2] + tree[root * 2 + 1];
31 }
32 int Query(int root, int l, int r, int ql, int qr)
33 {
34     if (l > qr || r < ql) return 0;
35     if (l >= ql&&r <= qr) return tree[root];
36     int mid = (l + r) / 2;
37     return Query(root * 2, l, mid, ql, qr) + Query(root * 2 + 1, mid + 1, r, ql, qr);
38 }
39 int main()
40 {
41     int n;
42     int Case = 1;
43     while (~scanf("%d", &n) && n)
44     {
45         Build(1, 1, n);
46         if (Case > 1) printf("\n");
47         printf("Case %d:\n", Case++);
48         while (~scanf("%s", s) && s[0] != 'E')
49         {
50             if (s[0] == 'S')
51             {
52                 int p, v;
53                 scanf("%d%d", &p, &v);
54                 Update(1, 1, n, p, v);
55             }
56             else
57             {
58                 int ql, qr;
59                 scanf("%d%d", &ql, &qr);
60                 printf("%d\n",Query(1, 1, n, ql, qr));
61             }
62         }
63     }
64     return 0;
65 }

View Code

 18、LA 5902 Movie collection

  题意:最初n个光盘从上到下编号也1~n,每次挑同一布置编号为x的光盘并将那在顶部,并且输出原本光盘所在位置上方之光盘数目。

  思路:单点更新,区间查询。线段树开4*(n+m),tree[i]啊1表示位置i有光盘。

bet365娱乐场官网 37bet365娱乐场官网 38

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 200100;
 5 int tree[maxn << 2];
 6 int Pos[maxn];
 7 char s[10];
 8 int n, m;
 9 void Build(int root, int l, int r)
10 {
11     if (l == r)
12     {
13         if (l <= m) tree[root] = 0;
14         else tree[root] = 1;
15         return;
16     }
17     int mid = (l + r) / 2;
18     Build(root * 2, l, mid);
19     Build(root * 2 + 1, mid + 1, r);
20     tree[root] = tree[root * 2] + tree[root * 2 + 1];
21 }
22 void Update(int root, int l, int r, int pos, int v)
23 {
24     if (pos<l || pos>r) return;
25     if (pos == l&&pos == r)
26     {
27         tree[root] = v;
28         return;
29     }
30     int mid = (l + r) / 2;
31     Update(root * 2, l, mid, pos, v);
32     Update(root * 2 + 1, mid + 1, r, pos, v);
33     tree[root] = tree[root * 2] + tree[root * 2 + 1];
34 }
35 int Query(int root, int l, int r, int ql, int qr)
36 {
37     if (l > qr || r < ql) return 0;
38     if (l >= ql&&r <= qr) return tree[root];
39     int mid = (l + r) / 2;
40     return Query(root * 2, l, mid, ql, qr) + Query(root * 2 + 1, mid + 1, r, ql, qr);
41 }
42 int main()
43 {
44     int t;
45     int Case = 1;
46     scanf("%d", &t);
47     while (t--)
48     {
49         scanf("%d%d", &n, &m);
50         Build(1, 1, n+m);
51         for (int i = 1; i <= n; i++) Pos[i] = i + m;
52         for(int i=1;i<=m;i++)
53         {
54             int num;
55             scanf("%d", &num);
56             int ans = Query(1, 1,n+m,1, Pos[num]-1);
57             Update(1, 1, n + m, Pos[num], 0);
58             Update(1, 1, n + m, m - i + 1, 1);
59             Pos[num] = m - i + 1;
60             if (i > 1) printf(" ");
61             printf("%d", ans);
62         }
63         printf("\n");
64     }
65     return 0;
66 }

View Code

  补:树状数组。

bet365娱乐场官网 39bet365娱乐场官网 40

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,m;
 6 const int maxn = 200100;
 7 int b[maxn];//树状数组
 8 int pos[maxn];
 9 int lowbit(int x)
10 {//得到x二进制表示中位数最低的1
11     return (x&(-x));
12 }
13 int Query(int k)
14 {//求前k个数的和,b[]为树状数组
15     int res = 0;
16     while (k)
17     {
18         res += b[k];
19         k -= lowbit(k);
20     }
21     return res;
22 }
23 void Update(int x, int k)
24 {//第x位加上k
25     while (x <= n+m)
26     {
27         b[x] += k;
28         x += lowbit(x);
29     }
30 }
31 int main()
32 {
33     int T;
34     scanf("%d", &T);
35     while (T--)
36     {
37         scanf("%d%d", &n,&m);
38         memset(b, 0, sizeof(b));
39         for (int i = 1; i <= n; i++)
40         {
41             pos[i] = i + m;
42             Update(pos[i], 1);
43         }
44         for (int i = 1; i <= m; i++)
45         {
46             int num;
47             scanf("%d", &num);
48             int ans = Query(pos[num] - 1);
49             Update(pos[num], -1);
50             Update(m - i + 1, 1);
51             pos[num] = m - i + 1;
52             if (i > 1) printf(" ");
53             printf("%d", ans);
54         }
55         printf("\n");
56     }
57     return 0;
58 }

View Code

 19、UVA 12299 RMQ with Shifts

  题意:每次询问区间极小值或用多个数变换。

  思路:单点更新,区间查询。

bet365娱乐场官网 41bet365娱乐场官网 42

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 100100;
 6 const int INF = 0x7fffffff;
 7 int tree[maxn << 2];
 8 int Pos[maxn];
 9 int Num[maxn];
10 char s[50];
11 int n, q;
12 void Build(int root, int l, int r)
13 {
14     if (l == r)
15     {
16         tree[root] = Num[l];
17         return;
18     }
19     int mid = (l + r) / 2;
20     Build(root * 2, l, mid);
21     Build(root * 2 + 1, mid + 1, r);
22     tree[root] = min(tree[root * 2],tree[root * 2 + 1]);
23 }
24 void Update(int root, int l, int r, int pos, int v)
25 {
26     if (pos<l || pos>r) return;
27     if (pos == l&&pos == r)
28     {
29         tree[root] = v;
30         return;
31     }
32     int mid = (l + r) / 2;
33     Update(root * 2, l, mid, pos, v);
34     Update(root * 2 + 1, mid + 1, r, pos, v);
35     tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
36 }
37 int Query(int root, int l, int r, int ql, int qr)
38 {
39     if (l > qr || r < ql) return INF;
40     if (l >= ql&&r <= qr) return tree[root];
41     int mid = (l + r) / 2;
42     return min(Query(root * 2, l, mid, ql, qr),Query(root * 2 + 1, mid + 1, r, ql, qr));
43 }
44 int main()
45 {
46     while (~scanf("%d%d",&n,&q))
47     {
48         for (int i = 1; i <= n; i++) scanf("%d", &Num[i]);
49         Build(1, 1, n);
50         for (int i = 1; i <= q; i++)
51         {
52             scanf("%s",s);
53             int p = strchr(s, '(') - s;
54             p++;
55             if (s[0] == 'q')
56             {
57                 int x = 0, y = 0;
58                 while (s[p] != ',') x = x * 10 + s[p] - '0',p++;
59                 p++;
60                 while (s[p] != ')') y = y * 10 + s[p] - '0',p++;
61                 printf("%d\n", Query(1, 1, n, x, y));
62             }
63             else
64             {
65                 int cnt = 0;
66                 while (s[p] != ')')
67                 {
68                     int tmp = 0;
69                     while (s[p] != ','&& s[p] != ')') tmp = tmp * 10 + s[p] - '0',p++;
70                     Pos[cnt++] =tmp;
71                     if (s[p] == ',') p++;
72                 }
73                 for (int i = 0; i < cnt; i++)
74                 {
75                     Update(1, 1, n, Pos[i], Num[Pos[(i + 1) % cnt]]);
76                 }
77                 for (int i = 0; i < cnt-1; i++) swap(Num[Pos[i]], Num[Pos[(i + 1)]]);
78             }
79         }
80     }
81     return 0;
82 }

View Code

 20、LA 4108 SKYLINE

  题意:有一对主次顺序的构筑物,每个建筑的覆盖值为夫所在[l,r]蒙,比该之前的构筑物高或者等于强之间隔长度的与。求所有的覆盖值的及。

  思路:线段树,每次插入一个建筑时更新并统计其覆盖值。

bet365娱乐场官网 43bet365娱乐场官网 44

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 100100;
 5 struct node
 6 {
 7     int maxh;
 8     int setv;//-1表示完全覆盖,-2表示杂区
 9 }tree[maxn << 2];
10 void PushUp(int root, int l, int r)
11 {
12     tree[root].maxh = max(tree[root * 2].maxh, tree[root * 2 + 1].maxh);
13     if (tree[root * 2].maxh == tree[root * 2 + 1].maxh&&tree[root * 2].setv == tree[root * 2 + 1].setv&&tree[root*2].setv!=-2)
14     {
15         tree[root].setv = -1;
16     }
17     else tree[root].setv = -2;
18 }
19 void PushDown(int root, int l, int r)
20 {
21     if (tree[root].setv >= 0)
22     {
23         tree[root * 2].maxh = tree[root * 2 + 1].maxh = tree[root].setv;
24         tree[root * 2].setv = tree[root * 2 + 1].setv = tree[root].setv;
25         tree[root].setv = -1;
26     }
27 }
28 void Build(int root, int l, int r)
29 {
30     if (l == r)
31     {
32         tree[root].maxh = 0;
33         tree[root].setv = -1;
34         return;
35     }
36     int mid = (l + r) / 2;
37     Build(root * 2, l, mid);
38     Build(root * 2 + 1, mid + 1, r);
39     PushUp(root,l,r);
40 }
41 int tans;
42 void Update(int root, int l, int r, int ul, int ur, int vh)
43 {
44     if (l > ur || r < ul) return;
45     if (tree[root].setv != -2 && tree[root].maxh > vh)return;
46     if (l >= ul&&r <= ur)
47     {
48         if (vh >= tree[root].maxh)
49         {
50             tree[root].maxh = vh;
51             tans += r - l + 1;
52             tree[root].setv = vh;
53             return;
54         }
55     }
56     if (l == r) return;
57     PushDown(root, l, r);
58     //printf("%d %d:%d %d\n", l, r, tree[root].maxh, tree[root].setv);
59     int mid = (l + r) / 2;
60     Update(root * 2, l, mid, ul, ur, vh);
61     Update(root * 2+1,mid+1,r, ul, ur, vh);
62     PushUp(root, l, r);
63 }
64 int main()
65 {
66     int c,n;
67     scanf("%d", &c);
68     while (c--)
69     {
70         int ans = 0;
71         scanf("%d", &n);
72         Build(1, 0, maxn-1);
73         for (int i = 1; i <= n; i++)
74         {
75             int l, r, h;
76             scanf("%d%d%d", &l, &r, &h);
77             tans = 0;
78             l++;
79             Update(1, 0, maxn - 1, l, r, h);
80             ans += tans;
81         }
82         printf("%d\n", ans);
83     }
84     return 0;
85 }

View Code

  补:简洁版:如果某个区间只发同等种高度,则setv=h;否则setv=0.

bet365娱乐场官网 45bet365娱乐场官网 46

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 100100;
 5 struct node
 6 {
 7     int maxh;
 8     int setv;
 9 }tree[maxn << 2];
10 void PushUp(int root, int l, int r)
11 {
12     tree[root].maxh = max(tree[root * 2].maxh, tree[root * 2 + 1].maxh);
13     if (tree[root * 2].setv == tree[root * 2 + 1].setv) tree[root].setv = tree[root * 2].setv;
14     else tree[root].setv = 0;
15 }
16 void PushDown(int root, int l, int r)
17 {
18     if (tree[root].setv >0)
19     {
20         tree[root * 2].maxh = tree[root * 2 + 1].maxh = tree[root].setv;
21         tree[root * 2].setv = tree[root * 2 + 1].setv = tree[root].setv;
22     }
23 }
24 void Build(int root, int l, int r)
25 {
26     if (l == r)
27     {
28         tree[root].maxh = 0;
29         tree[root].setv = 0;
30         return;
31     }
32     int mid = (l + r) / 2;
33     Build(root * 2, l, mid);
34     Build(root * 2 + 1, mid + 1, r);
35     PushUp(root,l,r);
36 }
37 int tans;
38 void Update(int root, int l, int r, int ul, int ur, int vh)
39 {
40     if (l > ur || r < ul) return;
41     if (vh<tree[root].setv)return;
42     if (l >= ul&&r <= ur)
43     {
44         if (vh >= tree[root].maxh)
45         {
46             tree[root].maxh = vh;
47             tans += r - l + 1;
48             tree[root].setv = vh;
49             return;
50         }
51     }
52     if (l == r) return;
53     PushDown(root, l, r);
54     //printf("%d %d:%d %d\n", l, r, tree[root].maxh, tree[root].setv);
55     int mid = (l + r) / 2;
56     Update(root * 2, l, mid, ul, ur, vh);
57     Update(root * 2+1,mid+1,r, ul, ur, vh);
58     PushUp(root, l, r);
59 }
60 int main()
61 {
62     int c,n;
63     scanf("%d", &c);
64     while (c--)
65     {
66         int ans = 0;
67         scanf("%d", &n);
68         Build(1, 0, maxn-1);
69         for (int i = 1; i <= n; i++)
70         {
71             int l, r, h;
72             scanf("%d%d%d", &l, &r, &h);
73             tans = 0;
74             l++;
75             Update(1, 0, maxn - 1, l, r, h);
76             ans += tans;
77         }
78         printf("%d\n", ans);
79     }
80     return 0;
81 }

View Code

 

相关文章