专栏首页小樱的经验随笔Vijos P1448 校门外的树【多解,线段树,树状数组,括号序列法+暴力优化】

Vijos P1448 校门外的树【多解,线段树,树状数组,括号序列法+暴力优化】

校门外的树

描述

校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两个操作: K=1,K=1,读入l、r表示在区间[l,r]中种上一种树,每次操作种的树的种类都不同 K=2,读入l,r表示询问l~r之间能见到多少种树 (l,r>0)

格式

输入格式

第一行n,m表示道路总长为n,共有m个操作 接下来m行为m个操作

输出格式

对于每个k=2输出一个答案

样例1

样例输入1

5 4
1 1 3
2 2 5
1 2 4
2 3 5

样例输出1

1
2

限制

1s

提示

范围:20%的数据保证,n,m<=100 60%的数据保证,n <=1000,m<=50000 100%的数据保证,n,m<=50000

来源

dejiyu@CSC WorkGroup

题目链接:https://vijos.org/p/1448

分析:这题目从上午九点写到下午四点,历经七个小时的磨难,只为给大家提供最优质的方法!

这道题我用了三种方法去解决!

第一种:线段树【时间花费最长,也最伤脑的写法】,做法是将[a,b]种上一种树,这个修改操作影响的询问满足,

询问区间与[a,b]有交,转化为统计总修改数-与某询问交为空集的修改数

对于一个修改操作[l,r],与它为空集的询问[a,b]满足a∈[1,l-1]或者b∈[r+1,n]

用两棵线段树维护,修改[l,r],将第一棵的[1,l-1]区间+1,第二棵[r+1,n]区间+1

询问[a,b],答案为之前的修改数-(第一棵单点询问b+第二棵单点询问a)

代码中线段树结点的l,r其实就是两棵线段树。。。标记永久化

下面给出线段树的代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int N=500050;
  4 int n,m;
  5 inline int read()
  6 {
  7     int x=0,f=1;
  8     char ch=getchar();
  9     while(ch<'0'||ch>'9')
 10     {
 11         if(ch=='-')
 12             f=-1;
 13         ch=getchar();
 14     }
 15     while(ch>='0'&&ch<='9')
 16     {
 17         x=x*10+ch-'0';
 18         ch=getchar();
 19     }
 20     return x*f;
 21 }
 22 inline void write(int x)
 23 {
 24     if(x<0)
 25     {
 26         putchar('-');
 27         x=-x;
 28     }
 29     if(x>9)
 30     {
 31         write(x/10);
 32     }
 33     putchar(x%10+'0');
 34 }
 35 struct Tree
 36 {
 37     int l,r;
 38     int left,right;
 39 }tree[N<<3];
 40 inline void buildtree(int x,int y,int pos)
 41 {
 42     tree[pos].left=x;
 43     tree[pos].right=y;
 44     if(x==y)
 45     {
 46         return;
 47     }
 48     int mid=(x+y)/2;
 49     buildtree(x,mid,pos*2);
 50     buildtree(mid+1,y,pos*2+1);
 51 }
 52 inline void insertl(int x,int y,int pos)
 53 {
 54     int l=tree[pos].left;
 55     int r=tree[pos].right;
 56     if(l==x&&r==y)
 57     {
 58         tree[pos].l++;
 59         return;
 60     }
 61     int mid=(l+r)/2;
 62     if(y<=mid)
 63         insertl(x,y,pos*2);
 64     else if(x>mid)
 65         insertl(x,y,pos*2+1);
 66     else
 67     {
 68         insertl(x,mid,pos*2);
 69         insertl(mid+1,y,pos*2+1);
 70     }
 71 }
 72 inline void insertr(int x,int y,int pos)
 73 {
 74     int l=tree[pos].left;
 75     int r=tree[pos].right;
 76     if(l==x&&r==y)
 77     {
 78         tree[pos].r++;
 79         return;
 80     }
 81     int mid=(l+r)/2;
 82     if(y<=mid)
 83         insertr(x,y,pos*2);
 84     else if(x>mid)
 85         insertr(x,y,pos*2+1);
 86     else
 87     {
 88         insertr(x,mid,pos*2);
 89         insertr(mid+1,y,pos*2+1);
 90     }
 91 }
 92 inline int askl(int k,int x)
 93 {
 94     int l=tree[k].left;
 95     int r=tree[k].right;
 96     if(l==r)
 97         return tree[k].l;
 98     int mid=(l+r)/2;
 99     if(x<=mid)
100         return tree[k].l+askl(k*2,x);
101     else return tree[k].l+askl(k*2+1,x);
102 }
103 inline int askr(int k,int x)
104 {
105     int l=tree[k].left;
106     int r=tree[k].right;
107     if(l==r)
108         return tree[k].r;
109     int mid=(l+r)/2;
110     if(x<=mid)
111         return tree[k].r+askr(k*2,x);
112     else return tree[k].r+askr(k*2+1,x);
113 }
114 int main()
115 {
116     n=read();
117     m=read();
118     int tot=0;
119     buildtree(0,n,1);
120     for(int i=1;i<=m;i++)
121     {
122         int t,a,b;
123         cin>>t>>a>>b;
124         if(t==1)
125         {
126             insertl(0,a-1,1);
127             insertr(b+1,n,1);
128             tot++;
129         }
130         else
131         {
132             int ans=askr(1,a)+askl(1,b);
133             write(tot-ans);
134             cout<<endl;
135         }
136     }
137     return 0;
138 }

第二种写法:树状数组

做法:这题是一条条线段,所以我们可以用线段树之类的东东来实现,然后感觉树状数组写起来简单一点所以就打了 开两个数组来存一个是开始的点的数量,一个是结束的 ,然后随便搞一下,最后输出就可以了

下面给出树状数组写法:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=50050;
 4 int l[N],r[N];
 5 int n,m;
 6 inline int read()
 7 {
 8     int x=0,f=1;
 9     char ch=getchar();
10     while(ch<'0'||ch>'9')
11     {
12         if(ch=='-')
13             f=-1;
14         ch=getchar();
15     }
16     while(ch>='0'&&ch<='9')
17     {
18         x=x*10+ch-'0';
19         ch=getchar();
20     }
21     return x*f;
22 }
23 inline void write(int x)
24 {
25     if(x<0)
26     {
27         putchar('-');
28         x=-x;
29     }
30     if(x>9)
31     {
32         write(x/10);
33     }
34     putchar(x%10+'0');
35 }
36 int lowbit(int x)
37 {
38     return x&-x;
39 }
40 void add(int x,int d,int c[])
41 {
42     while(x<=n)
43     {
44         c[x]+=d;
45         x+=lowbit(x);
46     }
47 }
48 int sum(int x,int c[])
49 {
50     int s=0;
51     while(x>0)
52     {
53         s+=c[x];
54         x-=lowbit(x);
55     }
56     return s;
57 }
58 int main()
59 {
60     int k,x,y;
61     n=read();
62     m=read();
63     for(int i=1;i<=m;i++)
64     {
65         cin>>k>>x>>y;
66         if(k==1)
67         {
68             add(x,1,l);
69             add(y,1,r);
70         }
71         else
72         {
73             write(sum(y,l)-sum(x-1,r));
74             cout<<endl;
75         }
76     }
77     return 0;
78 }

第三种方法:括号序列法【简称括号法】

假设有一个长度为10的数轴,我们要将区间[ 2 , 5 ]中种树,这时,我们将 2 处放一个左括号 " ( "  ,5处放一个 " )"  ,表示区间 [ 2 , 5 ]种了树。

查询某个区间树的种类,如区间[ 3 , 10],只需统计10之前(包括10)有多少个‘(’,统计3之前有多少个‘)’,(不包括3)。  

如下图所示:

以上就是括号序列的过程。简单的说,就是更新区间[a,b]时,点a记录左括号数,点b记录右括号数,查询区间[a,b]时,即为b之前(包括b)的左括号数-a之前的右括号数。

下面给出非常简练优秀的代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=50050;
 4 int l[N],r[N];
 5 int n,m;
 6 inline int read()
 7 {
 8     int x=0,f=1;
 9     char ch=getchar();
10     while(ch<'0'||ch>'9')
11     {
12         if(ch=='-')
13             f=-1;
14         ch=getchar();
15     }
16     while(ch>='0'&&ch<='9')
17     {
18         x=x*10+ch-'0';
19         ch=getchar();
20     }
21     return x*f;
22 }
23 inline void write(int x)
24 {
25     if(x<0)
26     {
27         putchar('-');
28         x=-x;
29     }
30     if(x>9)
31     {
32         write(x/10);
33     }
34     putchar(x%10+'0');
35 }
36 int main()
37 {
38     int k,x,y;
39     n=read();
40     m=read();
41     for(int i=1;i<=m;i++)
42     {
43         cin>>k>>x>>y;
44         if(k==1)
45         {
46             for(int j=x;j<=n;j+=j&-j)
47                 l[j]++;
48             for(int j=y;j<=n;j+=j&-j)
49                 r[j]++;
50         }
51         else
52         {
53             int ans=0;
54             for(int j=y;j;j-=j&-j)
55                 ans+=l[j];
56             for(int j=x-1;j;j-=j&-j)
57                 ans-=r[j];
58             write(ans);
59             cout<<endl;
60         }
61     }
62     return 0;
63 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ 1083: [SCOI2005]繁忙的都市【Kruscal最小生成树裸题】

    1083: [SCOI2005]繁忙的都市 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2925  Sol...

    Angel_Kitty
  • POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

    Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

    Angel_Kitty
  • Kruscal(最小生成树)算法模版

    1 const int maxn=400;//最大点数 2 const int maxm=10000;//最大边数 3 int n,m;//n表示点数,m...

    Angel_Kitty
  • 暑假(补)-5

    DFS全称Deep First Search,是一种遍历或搜索树或图的算法。在解决问题上,利用递归调用自身函数(这种说法好像不正确,领悟思想就好了)来实现搜索的...

    AngelNH
  • NYOJ 123 士兵杀敌(四) (线段树+树状数组)

    题目连接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=123

    Ch_Zaqdt
  • HDU 6621 (2019杭电第四场 1008) K-th Closest Distance (主席树 + 二分, 求第 k 小绝对值)

    题意:给出n m, 表示n个数,m组询问, 每组询问给出 l , r , p ,k 四个数,求[L,R]区间内 |p - a[i]|值第 k 小的数

    用户2965768
  • P2605 [ZJOI2010]基站选址

    题目描述 有N个村庄坐落在一条直线上,第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站,在第i个村庄建立基站的费用为Ci。...

    attack
  • 洛谷P4425 [HNOI/AHOI2018]转盘(线段树)

    首先猜一个结论:对于每次询问,枚举一个起点然后不断等到某个点出现时才走到下一个点一定是最优的。

    attack
  • P1400 塔

    题目描述 有N(2<=N<=600000)块砖,要搭一个N层的塔,要求:如果砖A在砖B上面,那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 10...

    attack
  • cf250D. The Child and Sequence(线段树 均摊复杂度)

    复杂度不知道是一个log还是两个log,大概是两个吧(线段树一个+最多改log次。)

    attack

扫码关注云+社区

领取腾讯云代金券