Mango DS Training #48 —线段树2 解题手记。数据结构–线段树。

Training address:
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38966#overview

线条树 好久没举行满忘记了
还得还学一下了

 

线条树–单点更新

A.Count Color — POJ 2777

HUD1166

立题初看不好下手,再想想,T<=30,这时想到颜色可以为此二进制来代表,然后父节点颜色种类也子节点的按位或得出的结果受到成为二进制时1的个数,然后就是无脑线段树了。。

题意:中文题

 

思路:线段树的单点更新

代码:

AC代码

图片 1图片 2

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define mem(a) memset(a,0,sizeof(a))
14 using namespace std;
15 
16 struct Node{
17     int l,r;
18     int sum;
19 };
20 Node Tree[100000<<2];
21 
22 void Build_Tree(int root, int l, int r)
23 {
24     Tree[root].l=l;
25     Tree[root].r=r;
26     if(l==r)
27     {
28         scanf("%d",&Tree[root].sum);
29         return;
30     }
31     int mid=l+r>>1;
32     Build_Tree(root*2+1,l,mid);
33     Build_Tree(root*2+2,mid+1,r);
34     Tree[root].sum=Tree[root*2+1].sum+Tree[root*2+2].sum;
35 }
36 
37 int Query(int root,int l,int r)
38 {
39     if(Tree[root].l==l && Tree[root].r==r)
40         return Tree[root].sum;
41     int mid=Tree[root].l+Tree[root].r>>1;
42     if(r<=mid)
43         return Query(root*2+1,l,r);
44     if(l>mid)
45         return Query(root*2+2,l,r);
46     else
47         return Query(root*2+1,l,mid)+Query(root*2+2,mid+1,r);
48 }
49 
50 void Update_One(int root,int l,int r,int p,int add)
51 {
52     if(l==r)
53     {
54         Tree[root].sum += add;
55         return;
56     }
57     int mid=l+r>>1;
58     if(p<=mid)  Update_One(root*2+1,l,mid,p,add);
59     else Update_One(root*2+2,mid+1,r,p,add);
60     Tree[root].sum=Tree[root*2+1].sum + Tree[root*2+2].sum;
61 }
62 
63 int main()
64 {
65     int t,c=0,n,l,r;
66     string s;
67     scanf("%d",&t);
68     while(t--){
69             printf("Case %d:\n",++c);
70         scanf("%d",&n);
71         mem(Tree);
72         Build_Tree(0,0,n-1);
73         while(cin>>s&&s!="End")
74         {
75             scanf("%d%d",&l,&r);
76             if(s=="Query")  printf("%d\n",Query(0,l-1,r-1));
77             else if(s=="Add")  Update_One(0,0,n-1,l-1,r);
78             else Update_One(0,0,n-1,l-1,-r);
79         }
80     }
81    return 0;
82 }

View
Code

图片 3图片 4

 HDU1754

#include <iostream>
#include <cstdio>
#include <utility>
#include <cstdlib>
using namespace std;
#define N 100010

struct node
{
    int mark;
    int sum;
}tree[4*N];

void pushup(int rt)
{
    tree[rt].sum = tree[2*rt].sum | tree[2*rt+1].sum;
}

void build(int l,int r,int rt)
{
    tree[rt].sum = 1;
    tree[rt].mark = 1;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
    pushup(rt);
}

void pushdown(int l,int r,int rt)
{
    if(!tree[rt].mark)
        return;
    if(tree[rt].mark)
    {
        tree[2*rt].sum = tree[2*rt+1].sum = tree[rt].sum;
        tree[2*rt].mark = tree[2*rt+1].mark = tree[rt].mark;
        tree[rt].mark = 0;
    }
}

void make(int l,int r,int aa,int bb,int co,int rt)
{
    if(aa<=l && bb>=r)
    {
        tree[rt].mark = 1;
        tree[rt].sum = 1<<(co-1);
        return;
    }
    pushdown(l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        make(l,mid,aa,bb,co,2*rt);
    if(bb>mid)
        make(mid+1,r,aa,bb,co,2*rt+1);
    pushup(rt);
}

int query(int l,int r,int aa,int bb,int rt)
{
    if(aa>r||bb<l)
        return 0;
    if(aa<=l&&bb>=r)
    {
        return tree[rt].sum;
    }
    pushdown(l,r,rt);
    int mid = (l+r)/2;
    return query(l,mid,aa,bb,2*rt)|query(mid+1,r,aa,bb,2*rt+1);
}

int main()
{
    int n,t,o;
    int i;
    int aa,bb,co;
    char ss[5];
    scanf("%d%d%d",&n,&t,&o);
    build(1,n,1);
    int cnt;
    for(i=0;i<o;i++)
    {
        scanf("%s",ss);
        if(ss[0] == 'C')
        {
            scanf("%d%d%d",&aa,&bb,&co);
            make(1,n,aa,bb,co,1);
        }
        else if(ss[0] == 'P')
        {
            scanf("%d%d",&aa,&bb);
            int res;
            if(aa<=bb)
                res = query(1,n,aa,bb,1);
            else
                res = query(1,n,bb,aa,1);
            cnt = 0;
            while(res)
            {
                if(res&1)
                    cnt++;
                res>>=1;
            }
            printf("%d\n",cnt);
        }
    }
    return 0;
}

题意:中文题

View Code

思路:线段树的单点更新

 

AC代码

图片 5图片 6

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define mem(a) memset(a,0,sizeof(a))
14 using namespace std;
15 
16 struct Node{
17     int l,r;
18     int m;
19 };
20 
21 int date,p;
22 Node Tree[222222<<2];
23 
24 void Build_Tree(int root, int l, int r)
25 {
26     Tree[root].l=l;
27     Tree[root].r=r;
28     if(l==r)
29     {
30         scanf("%d",&Tree[root].m);
31         return;
32     }
33     int mid=l+r>>1;
34     Build_Tree(root*2,l,mid);
35     Build_Tree(root*2+1,mid+1,r);
36     Tree[root].m = max(Tree[root*2].m,Tree[root*2+1].m);
37 }
38 
39 int Query(int root, int l, int r)
40 {
41     if(Tree[root].l==l && Tree[root].r==r)
42         return Tree[root].m;
43     int mid=Tree[root].l+Tree[root].r>>1;
44     if(r<=mid)
45         return Query(root*2,l,r);
46     if(l>mid)
47         return Query(root*2+1,l,r);
48     else
49         return max(Query(root*2,l,mid),Query(root*2+1,mid+1,r));
50 }
51 
52 void Update_One(int root,int l,int r)
53 {
54     if(l==r)
55     {
56         Tree[root].m=date;
57         return;
58     }
59     int mid=l+r>>1;
60     if(p<=mid)  Update_One(root*2,l,mid);
61     else  Update_One(root*2+1,mid+1,r);
62     Tree[root].m = max(Tree[root*2].m,Tree[root*2+1].m);
63 }
64 
65 int main()
66 {
67     int n,q,l,r;
68     char c;
69     while(~scanf("%d%d",&n,&q)){
70         Build_Tree(1,1,n);
71         while(q--){
72             getchar();
73             scanf("%c%d%d",&c,&l,&r);
74             if(c=='Q')  printf("%d\n",Query(1,l,r));
75             else  {p=l,date=r;Update_One(1,1,n);}
76         }
77     }
78    return 0;
79 }

View
Code

B.Who Gets the Most Candies — POJ 2886

HUD1556

(题解借鉴: ahfywff)

题意:输入n 然后n个区间操作 l,r 对区间的气球涂油漆 ,最后输出每个气球为涂了聊坏

   
本题利用反素数的概念。反素数的概念:对于其余正整数x,其约数的个数记做f(x)。例如f(1)=1,f(6)=4。如果有正整数x满足:对于任意i(0<i<x),都生f(i)<f(x),则称x为反素数。对于主题,设pos为未超过N的反素数,则第pos单出圈的儿女取的糖最多,为pos的横数独数。

思路:线段树的距离更新

AC代码

图片 7图片 8

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define lson l,mid,rt<<1
14 #define rson mid+1,r,rt<<1|1
15 #define len (Tr[rt].r-Tr[rt].l+1)
16 #define mem(a) memset(a,0,sizeof(a))
17 using namespace std;
18 
19 struct Node{
20     int l,r;
21     int v,add;
22 };
23 Node Tr[200005<<2];
24 
25 void Push_up(int rt){
26     Tr[rt].v=Tr[rt<<1].v+Tr[rt<<1|1].v;
27 }
28 
29 void Push_Down(int rt, int m){
30     Tr[rt<<1].add+=Tr[rt].add;
31     Tr[rt<<1|1].add+=Tr[rt].add;
32     Tr[rt<<1].v+=Tr[rt].add*(m-(m>>1));
33     Tr[rt<<1|1].v+=Tr[rt].add*(m>>1);
34     Tr[rt].add=0;
35 }
36 
37 void Build_Tree(int l,int r,int rt){
38     Tr[rt].l=l,Tr[rt].r=r;
39     if(l==r) return;
40     int mid=l+r>>1;
41     Build_Tree(lson);
42     Build_Tree(rson);
43     Push_up(rt);
44 }
45 
46 void Updata(int l,int r,int rt){
47     if(l==Tr[rt].l && r==Tr[rt].r){
48         Tr[rt].v+=len;
49         Tr[rt].add++;
50         return;
51     }
52     int mid=Tr[rt].l+Tr[rt].r>>1;
53     if(r<=mid) Updata(l,r,rt<<1);
54     else if(l>mid) Updata(l,r,rt<<1|1);
55     else{
56         Updata(lson);
57         Updata(rson);
58     }
59     Push_up(rt);
60 }
61 
62 int Query(int l,int r,int rt){
63     if(l==Tr[rt].l && r==Tr[rt].r) return Tr[rt].v;
64     if(Tr[rt].add!=0) Push_Down(rt,len);
65     int mid=Tr[rt].l+Tr[rt].r>>1;
66     if(r<=mid) return Query(l,r,rt<<1);
67     if(l>mid) return Query(l,r,rt<<1|1);
68     else return Query(l,mid,rt<<1)+Query(mid+1,r,rt<<1|1);
69 }
70 
71 int main(){
72     int n,q,l,r;
73     while(scanf("%d",&n) && n!=0){
74         mem(Tr);
75         Build_Tree(1,n,1);
76         q=n;
77         while(q--){
78             scanf("%d%d",&l,&r);
79             Updata(l,r,1);
80         }
81         for(int i=1; i<=n; i++){
82             if(i!=1) printf(" ");
83             printf("%d",Query(i,i,1));
84         }
85         printf("\n");
86     }
87     return 0;
88 }

View
Code

代码来日上及

HDU1394

HDU2795

题意:

思路:

 AC代码

图片 9图片 10

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define lson l,mid,rt<<1
14 #define rson mid+1,r,rt<<1|1
15 #define len (Tr[rt].r-Tr[rt].l+1)
16 #define mem(a) memset(a,0,sizeof(a))
17 using namespace std;
18 const int N=200005;
19 struct Node{
20     int l,r;
21     int maxn;
22 }Tr[N<<2];
23 int w,ans[N];
24 
25 void Push_up(int rt){
26     Tr[rt].maxn=max(Tr[rt<<1].maxn,Tr[rt<<1|1].maxn);
27 }
28 
29 void Build_Tree(int l, int r, int rt){
30     Tr[rt].l=l,Tr[rt].r=r;
31     if(l==r){
32         Tr[rt].maxn=w; return;
33     }
34     int mid=l+r>>1;
35     Build_Tree(lson);
36     Build_Tree(rson);
37     Push_up(rt);
38 }
39 
40 void Updata_One(int l,int r,int rt,int data,int n){
41     int mid=l+r>>1;
42     if(Tr[rt].maxn<data) {ans[n]=-1;return;}
43     else if(l==r){
44         Tr[rt].maxn-=data;
45        ans[n]=Tr[rt].l;
46        return;
47     }
48     else if(Tr[rt<<1].maxn>=data)
49         Updata_One(lson,data,n);
50     else if(Tr[rt<<1|1].maxn>=data)
51         Updata_One(rson,data,n);
52     Push_up(rt);
53 }
54 
55 int main(){
56     int h,n,x;
57     while(scanf("%d%d%d",&h,&w,&n)!=EOF){
58         mem(Tr),mem(ans);
59         h = h < N ? h : N;
60         Build_Tree(1,h,1);
61         for(int i=1; i<=n; i++){
62             scanf("%d",&x);
63             Updata_One(1,h,1,x,i); printf("%d\n",ans[i]);
64         }
65     }
66    return 0;
67 }

View
Code

HDU1698

  
出圈过程有点类似约瑟夫环。假设当前出圈的凡剩下孩子受到之第K只,他手中的数字为A。

题意:给一个数组 再受Q个操作 每次用x y区间内的数换成z 求最后往往组的跟

    若A大于零,下一个出圈的哪怕相应是多余孩子遭到之第(K-1+A-1)%n+1独;

思路:线段树的距离替换

    若A小于零,下一个出圈的即使该是多余孩子吃之第((K-1+A)%n+n)%n+1单。

AC代码

图片 11图片 12

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define lson l,mid,rt<<1
14 #define rson mid+1,r,rt<<1|1
15 #define len (Tr[rt].r-Tr[rt].l+1)
16 #define mem(a) memset(a,0,sizeof(a))
17 using namespace std;
18 
19 struct Node{
20     int l,r;
21     int val;
22     int lazy;
23 };
24 
25 Node Tr[100000<<2];
26 
27 void Push_up(int rt){
28     Tr[rt].val=Tr[rt<<1].val+Tr[rt<<1|1].val;
29 }
30 
31 void Push_Down(int rt,int m){
32     Tr[rt<<1].lazy=Tr[rt<<1|1].lazy=Tr[rt].lazy;
33     Tr[rt<<1].val=Tr[rt].lazy*(m-(m>>1));
34     Tr[rt<<1|1].val=Tr[rt].lazy*(m>>1);
35     Tr[rt].lazy=0;
36 }
37 
38 void Build(int l, int r, int rt){
39     Tr[rt].l=l;
40     Tr[rt].r=r;
41     if(l==r) {Tr[rt].val=1;return;}
42     int mid=l+r>>1;
43     Build(lson);
44     Build(rson);
45     Push_up(rt);
46 }
47 
48 void Updata(int l,int r,int rt,int data){
49     if(Tr[rt].l==l && Tr[rt].r==r){
50         Tr[rt].lazy=data;
51         Tr[rt].val=data*len;
52         return;
53     }
54     if (Tr[rt].lazy) Push_Down(rt,len);
55     int mid=Tr[rt].l+Tr[rt].r>>1; //printf("%d pp\n",mid);
56     if(r<=mid) Updata(l,r,rt<<1,data);
57     else if(l>mid) Updata(l,r,rt<<1|1,data);
58     else {Updata(lson,data);Updata(rson,data);}
59     Push_up(rt);
60 }
61 
62 int main()
63 {
64     int t,n,m,l,r,data,T=0;
65     scanf("%d",&t);
66     while(t--){
67         mem(Tr);
68         scanf("%d",&n);
69         Build(1,n,1);
70         scanf("%d",&m);
71         while(m--){
72             scanf("%d%d%d",&l,&r,&data);
73             Updata(l,r,1,data);
74         }
75         printf("Case %d: The total value of the hook is %d.\n",++T,Tr[1].val);
76     }
77    return 0;
78 }

View
Code

POJ2828

POJ2886

POJ3468

题意:给n个数
然后Q个操作,Q代表查询区间a,b的以及,C表示针对区间a,b内的每个数加c

思路:线段树区间更新 lazy思想
在创新的时候特别注意,一定要是联合考虑,比如lazy用于记录之是孩子节点的增量
不要还多sum 不要还多 逻辑要正确

AC代码 

图片 13图片 14

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define lson l,mid,rt<<1
14 #define rson mid+1,r,rt<<1|1
15 #define len (Tr[rt].r-Tr[rt].l+1)
16 #define mem(a) memset(a,0,sizeof(a))
17 using namespace std;
18 struct Node{
19     ll l,r;
20     ll sum,add;
21 }Tr[100000<<2];
22 
23 void Push_up(ll rt){
24     Tr[rt].sum=Tr[rt<<1].sum + Tr[rt<<1|1].sum;
25 }
26 
27 void Push_down(ll rt, ll m){
28     Tr[rt<<1].add+=Tr[rt].add;
29     Tr[rt<<1|1].add+=Tr[rt].add;
30     Tr[rt<<1].sum+=Tr[rt].add*(m-(m>>1));
31     Tr[rt<<1|1].sum+=Tr[rt].add*(m>>1);
32     Tr[rt].add=0;
33 }
34 
35 void Build_Tree(ll l, ll r, ll rt){
36     Tr[rt].l=l, Tr[rt].r=r;
37     if(l==r){
38         scanf("%lld",&Tr[rt].sum);
39         return;
40     }
41     ll mid=l+r>>1;
42     Build_Tree(lson);
43     Build_Tree(rson);
44     Push_up(rt);
45 }
46 
47 void Updata(ll l, ll r, ll rt, ll data){
48     if(l==Tr[rt].l && r==Tr[rt].r){
49         Tr[rt].sum+=data*len;
50         Tr[rt].add+=data;
51         return;
52     }
53     if(Tr[rt].add) Push_down(rt,len);
54     ll mid = Tr[rt].l+Tr[rt].r>>1;
55     if(r<=mid) Updata(l,r,rt<<1,data);
56     else if(l>mid) Updata(l,r,rt<<1|1,data);
57     else{
58         Updata(lson,data);
59         Updata(rson,data);
60     }
61     Push_up(rt);
62 }
63 
64 ll Query(ll l, ll r, ll rt){
65     if(Tr[rt].l==l && Tr[rt].r==r)
66         return Tr[rt].sum;
67     if(Tr[rt].add) Push_down(rt,len);
68     ll mid=Tr[rt].l+Tr[rt].r>>1;
69     if(r<=mid) return Query(l,r,rt<<1);
70     if(l>mid) return Query(l,r,rt<<1|1);
71     else return Query(lson) + Query(rson);
72 }
73 
74 int  main(){
75     ll n,q,l,r,c;
76     char s;
77     while(cin>>n>>q){
78         mem(Tr);
79         Build_Tree(1,n,1);
80         while(q--){
81         cin>>s;
82         if(s=='Q'){
83             scanf("%lld%lld",&l,&r);
84             ll ans=Query(l,r,1);
85             printf("%lld\n",ans);
86         }
87         if(s=='C'){
88             scanf("%lld%lld%lld",&l,&r,&c);
89             Updata(l,r,1,c);
90         }
91         }
92     }
93     return 0;
94 }

View
Code

POJ3264

题意:给您n个数 然后q个查询
查询区间l,r内最老价值与无限小值的异

思路:区间查询
连更新都不用此可以就此各自就此一个变量来抱查询区间的最可怜无比小值
省去矣历次要查询最老最小各个一蹩脚 我以这边一直用maxn[0]
minn[0]

图片 15图片 16

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define lson l,mid,rt<<1
14 #define rson mid+1,r,rt<<1|1
15 #define mem(a) memset(a,0,sizeof(a))
16 using namespace std;
17 
18 ///poj3264
19 const int N=50000;
20 int maxn[N<<2];
21 int minn[N<<2];
22 
23 void Push_up(int rt){
24     maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);
25     minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
26 }
27 
28 void Build(int l, int r, int rt){
29     if(l==r){
30         int vv;
31         scanf("%d",&vv);
32         maxn[rt]=minn[rt]=vv;
33         return;
34     }
35     int mid=l+r>>1;
36     Build(lson);
37     Build(rson);
38     Push_up(rt);
39 }
40 
41 void Query(int l,int r,int rt,int L, int R){
42     if(l==L && r==R){
43         maxn[0]=max(maxn[0],maxn[rt]);
44         minn[0]=min(minn[0],minn[rt]);
45         return;
46     }
47     int mid=L+R>>1;
48     if(r<=mid) Query(l,r,rt<<1,L,mid);
49     else if(l>mid) Query(l,r,rt<<1|1,mid+1,R);
50     else Query(lson,L,mid),Query(rson,mid+1,R);
51 }
52 
53 int main(){
54     int n,q,l,r;
55     while(scanf("%d%d",&n,&q)!=EOF){
56         Build(1,n,1);
57         while(q--){
58             maxn[0]=0,minn[0]=99999999;
59             scanf("%d%d",&l,&r);
60             Query(l,r,1,1,n);
61             printf("%d\n",maxn[0]-minn[0]);
62         }
63     }
64     return 0;
65 }

View Code

 

 

 

 HDU5685

题意:给你一个字符串
求l,r区间内字符串的哈希值,哈希公式为 H(s)=∏i≤len(s)i=1(Si−28) (mod 9973)

思路:线段树查找
不欲更新

AC代码:

图片 17图片 18

 1 #include "iostream"
 2 #include "string.h"
 3 #include "stack"
 4 #include "queue"
 5 #include "string"
 6 #include "vector"
 7 #include "set"
 8 #include "map"
 9 #include "algorithm"
10 #include "stdio.h"
11 #include "math.h"
12 #define ll long long
13 #define lson l,mid,rt<<1
14 #define rson mid+1,r,rt<<1|1
15 #define mem(a) memset(a,0,sizeof(a))
16 using namespace std;
17 const int mod=9973;
18 struct Node{
19     int l,r;
20     int s;
21 };
22 Node Tr[100005<<2];
23 char ss[100005];
24 void Push_up(int rt){
25     Tr[rt].s=(Tr[rt<<1].s*Tr[rt<<1|1].s)%mod;
26 }
27 
28 void Build(int l,int r, int rt){
29     Tr[rt].l=l,Tr[rt].r=r;
30     if(l==r){
31         Tr[rt].s=ss[l-1]-28;
32         return;
33     }
34     int mid=l+r>>1;
35     Build(lson);
36     Build(rson);
37     Push_up(rt);
38 }
39 
40 int Query(int l, int r, int rt){
41     if(Tr[rt].l==l && Tr[rt].r==r)
42         return Tr[rt].s;
43     int mid=Tr[rt].l+Tr[rt].r>>1;
44     if(r<=mid) return Query(l,r,rt<<1);
45     if(l>mid) return Query(l,r,rt<<1|1);
46     else return Query(lson)*Query(rson)%mod;
47 }
48 
49 int main()
50 {
51     int n,l,r;
52     while(cin>>n){
53         mem(ss),mem(Tr);
54         cin>>ss;
55         int len=strlen(ss);
56         Build(1,len,1);
57         while(n--){
58             scanf("%d%d",&l,&r);
59             cout<<Query(l,r,1)%mod<<endl;
60         }
61     }
62     return 0;
63 }

View
Code

   
问题之第一是何许求得出圈孩子的旧位置,线段树的每个节点的sum存储了所当间隔还有小子女留,查询节点rt中第num只儿女的原位置时,如果num<=st[2*rt].sum,则以左孩子节点受到查询第num单子女的原来位置;否则在右边孩子节点受到查询第num-st[2*rt].sum个男女的原有位置。

线树+区间离散化(校赛的一个问题)

 

POJ2528

  代码:

POJ3225

POJ1436

POJ2991

POJ3667

 

图片 19图片 20

/*12152 KB    1079 ms*/
#include <iostream>
#include <cstdio>
using namespace std;
#define N 500010

int anti[37]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,
           55440,83160,110880,166320,221760,277200,332640,498960,500001};
int factor[37]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521};

int tree[4*N];
char name[N][11];
int num[N];

void build(int l,int r,int rt)
{
    tree[rt] = r-l+1;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}

int query(int l,int r,int pos,int rt)
{
    tree[rt]--;
    if(l == r)
        return l;
    int mid = (l+r)/2;
    if(pos<=tree[2*rt])
        return query(l,mid,pos,2*rt);
    else
        return query(mid+1,r,pos-tree[2*rt],2*rt+1);
}

int main()
{
    int n,k,pos,Maxcandy,i;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        i=0;
        int CN = n;
        while(anti[i]<=n)
            i++;
        pos = anti[i-1];
        Maxcandy = factor[i-1];
        build(1,n,1);
        for(i=1;i<=n;i++)
        {
            scanf("%s %d",name[i],&num[i]);
        }
        int flag;
        for(i=1;i<=pos;i++)
        {
            n--;
            flag = query(1,CN,k,1);
            if(n==0)
                break;
            if(num[flag]>0)
                k = (k + num[flag] - 2)%n + 1;
            else
                k = ((k + num[flag] - 1)%n+n)%n + 1;
        }
        printf("%s %d\n",name[flag],Maxcandy);
    }
}

View Code

 

G.Fast Matrix Operations —UVA 11992

  这题其实呢无太为难抓,关键是各国面只要维护及,我写了少单多钟头啊,最后要略微地方尚未照料到,哎,太弱咯。。感觉好以维护值方面尚不一一点会。
这书看行数不跳20,想到以各级一行还修建同等颗线段树,然后就为吧。。代码来硌长,将就着看吧。

(A.M : Attention to Maintain)

 

代码:

图片 21图片 22

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <cstdlib>
#define Mod 1000000007
using namespace std;
#define N 1000010

struct node
{
    int mini,maxi,sum;
    int addmark,setmark;
}tree[21][4*N];

int i;

void pushup(int i,int rt)
{
    tree[i][rt].sum = tree[i][2*rt].sum + tree[i][2*rt+1].sum;
    tree[i][rt].mini = min(tree[i][2*rt].mini,tree[i][2*rt+1].mini);
    tree[i][rt].maxi = max(tree[i][2*rt].maxi,tree[i][2*rt+1].maxi);
}

void build(int i,int l,int r,int rt)
{
    tree[i][rt].sum = tree[i][rt].mini = tree[i][rt].maxi = 0;
    tree[i][rt].setmark = -1;
    tree[i][rt].addmark = 0;
    if(l == r)
        return;
    int mid = (l+r)/2;
    build(i,l,mid,2*rt);
    build(i,mid+1,r,2*rt+1);
    pushup(i,rt);
}

void pushdown(int i,int l,int r,int rt)
{
    if(tree[i][rt].setmark == -1 && tree[i][rt].addmark == 0)
        return;
    int mid = (l+r)/2;
    if(tree[i][rt].setmark >= 0)
    {
        tree[i][2*rt].sum = tree[i][rt].setmark*(mid-l+1);
        tree[i][2*rt+1].sum = tree[i][rt].setmark*(r-mid);
        tree[i][2*rt].mini = tree[i][2*rt+1].mini = tree[i][rt].setmark;  //A.M 
        tree[i][2*rt].maxi = tree[i][2*rt+1].maxi = tree[i][rt].setmark;  //A.M
        tree[i][2*rt].addmark = tree[i][2*rt+1].addmark = 0;  // 这个要写 
        tree[i][2*rt].setmark = tree[i][2*rt+1].setmark = tree[i][rt].setmark;
        tree[i][rt].setmark = -1;
    }
    if(tree[i][rt].addmark > 0)
    {
        tree[i][2*rt].sum += tree[i][rt].addmark*(mid-l+1);
        tree[i][2*rt+1].sum += tree[i][rt].addmark*(r-mid);
        tree[i][2*rt].maxi += tree[i][rt].addmark;  //A.M
        tree[i][2*rt].mini += tree[i][rt].addmark;  //A.M
        tree[i][2*rt+1].maxi += tree[i][rt].addmark;  //A.M
        tree[i][2*rt+1].mini += tree[i][rt].addmark;  //A.M
        tree[i][2*rt].addmark += tree[i][rt].addmark;
        tree[i][2*rt+1].addmark += tree[i][rt].addmark;
        tree[i][rt].addmark = 0;
    }
}

void add(int l,int r,int aa,int bb,int val,int rt)
{
    if(aa>r||bb<l)
        return;
    if(aa<=l&&bb>=r)
    {
        tree[i][rt].addmark += val;
                                   //tree[i][rt].setmark = -1;  --不要写这个 
        tree[i][rt].sum += (r-l+1)*val;
        tree[i][rt].maxi += val;
        tree[i][rt].mini += val;
        return;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        add(l,mid,aa,bb,val,2*rt);
    if(bb>mid)
        add(mid+1,r,aa,bb,val,2*rt+1);
    pushup(i,rt);
}

void setval(int l,int r,int aa,int bb,int val,int rt)
{
    if(aa>r||bb<l)
        return;
    if(aa<=l&&bb>=r)
    {
        tree[i][rt].setmark = val;
        tree[i][rt].addmark = 0;
        tree[i][rt].sum = val*(r-l+1);
        tree[i][rt].maxi = tree[i][rt].mini = val;
        return;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        setval(l,mid,aa,bb,val,2*rt);
    if(bb>mid)
        setval(mid+1,r,aa,bb,val,2*rt+1);
    pushup(i,rt);
}

struct node_ans
{
    int sum;
    int mini,maxi;
};

node_ans query(int l,int r,int aa,int bb,int rt)
{
    node_ans res,ka1,ka2;
    if(aa<=l && bb>=r)
    {
        res.sum = tree[i][rt].sum;
        res.maxi = tree[i][rt].maxi;
        res.mini = tree[i][rt].mini;
        return res;
    }
    pushdown(i,l,r,rt);
    int mid = (l+r)/2;
    if(bb<=mid)
        return query(l,mid,aa,bb,2*rt);
    else if(aa>mid)
        return query(mid+1,r,aa,bb,2*rt+1);
    else
    {
        ka1 = query(l,mid,aa,bb,2*rt);
        ka2 = query(mid+1,r,aa,bb,2*rt+1);
        res.sum = ka1.sum + ka2.sum;
        res.maxi = max(ka1.maxi,ka2.maxi);
        res.mini = min(ka1.mini,ka2.mini);
        return res;
    }
}

int main()
{
    int r,c,m;
    int k,zuo;
    int x1,y1,x2,y2,val;
    int sum,mmax,mmin;
    while(scanf("%d%d%d",&r,&c,&m)!=EOF)
    {
        for(i=1;i<=r;i++)
        {
            build(i,1,c,1);
        }
        for(k=0;k<m;k++)
        {
            scanf("%d",&zuo);
            if(zuo == 1)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
                for(i=x1;i<=x2;i++)
                {
                    add(1,c,y1,y2,val,1);
                }
            }
            else if(zuo == 2)
            {
                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
                for(i=x1;i<=x2;i++)
                {
                    setval(1,c,y1,y2,val,1);
                }
            }
            else 
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                node_ans la;
                sum = 0;
                mmax = -Mod;
                mmin = Mod;
                for(i=x1;i<=x2;i++)
                {
                    la = query(1,c,y1,y2,1);
                    sum += la.sum;
                    mmax = max(mmax,la.maxi);
                    mmin = min(mmin,la.mini);
                }
                printf("%d %d %d\n",sum,mmin,mmax);
            }
        }
    }
}

View Code

 

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注