POJ3368(Frequent values)--线段树

题目在这里

3368

Accepted

7312K

1829MS

C++

6936B

题意为给你一组数据，再给定一组区间，问你这个区间内出现次数最多的元素的次数是多少。

我还记得这题是学校校赛基础的题目，当时懵懵懂懂的用分治交了6次TLE。知道了线段树之后才后悔每更早的认识她。

一段区间内的多次出现的数的次数，在线段树查询中有以下几种情况

1.次数最多的都集中在某一结点的左区间内

2.次数最多的都集中在某一结点的有区间内

3.次数最多的在左右两边都有，这时maxCount ==左右两边的maxCount之和

在增加时，如果要加的区间正好覆盖一个节点，则增加其节点的Inc值，不再往下走，否则要更新nSum(加上本次增量),再将增量往下传。这样更新的复杂度就是O(log(n))在查询时，如果待查区间不是正好覆盖一个节点，就将节点的Inc往下带，然后将Inc代表的所有增量累加到nSum上后将Inc清0，接下来再往下查询。

  1 /*************************************************************************
  2     > File Name: poj3368rmq.cpp
  3     > Author: YeGuoSheng
  4     > Description:  
  5     > Created Time: 2019年07月11日 星期四 15时34分56秒
  6  ************************************************************************/
  7 
  8 #include
  9 #include
 10 #include
 11 #include
 12 #include
 13 #include
 14 #include
 15 #include<set>
 16 #include
 17 #include
 18 #include<string>
 19 #include
 20 #include
 21 using namespace std;
 22 
 23 template 
 24 struct node
 25 {
 26     int l;
 27     int r;//左右区间端点
 28     T value;
 29     T add;
 30     int lCount;//元素在左边的计数
 31     int rCount;//元素在右边的计数
 32     int maxCount;//总计出现的次数
 33     int Len()const;
 34     int Mid()const;
 35 };
 36 
 37 template 
 38 int node::Mid()const
 39 {
 40     return (r  + l )/ 2;
 41 }
 42 
 43 template
 44 int node::Len()const
 45 {
 46     return (r - l ) +1;
 47 }
 48 
 49 template
 50 class IntervalTree
 51 {
 52 protected:
 53     int n;
 54     node*tree;
 55 public:
 56     IntervalTree(int n);
 57     ~IntervalTree();
 58     void BuildTree(int v,int l,int r);
 59     void Add(int v,int l,int r,T m);
 60     T Query(int v,int l,int r);
 61     void Insert(int v,int i,T value);
 62     void BuildCount(int v,int l,int r);
 63     int FindIndexInTree(int v,int y);//在数组下标为u的在树中的下标
 64 };
 65 
 66 template
 67 IntervalTree::IntervalTree(int n)
 68 {
 69     this->n = n;
 70     tree = new node[4*n];
 71 }
 72 
 73 template
 74 IntervalTree::~IntervalTree()
 75 {
 76     delete []tree;
 77 }
 78 
 79 template
 80 void IntervalTree::BuildTree(int v ,int l,int r)
 81 {
 82     tree[v].l =l;
 83     tree[v].r = r;
 84     tree[v].add = 0;
 85     tree[v].value = 0;
 86     if(l == r)//相等
 87     {
 88         tree[v].lCount =tree[v].rCount = tree[v].maxCount = 1;
 89         return ;
 90     }
 91     int mid =(l + r) /2;//二分
 92     BuildTree(v* 2+1,l,mid);
 93     BuildTree(v*2+2,mid+1,r);
 94     tree[v].value = tree[2*v+1].value + tree[2*v+2].value;
 95 }
 96 
 97 
 98 template
 99 int IntervalTree::FindIndexInTree(int v,int u)
100 {
101     if( tree[v].l == u && tree[v].r == u)
102     {
103         return v;
104     }
105     else
106     {
107         int mid = (tree[v].l + tree[v].r) / 2;
108         if(u <= mid)
109         {
110             FindIndexInTree(v * 2+1,u);
111         }
112         else
113         {
114             FindIndexInTree(v * 2+2,u);
115         }
116     }
117 }
118 
119 template
120 void IntervalTree::BuildCount(int v,int l ,int r)
121 {
122     tree[v].l = l;
123     tree[v].r = r;
124     if(l == r)
125     {
126         tree[v].lCount = tree[v].rCount =tree[v].maxCount = 1; 
127         return ;
128     }
129     int mid  = (l + r )/ 2;
130     BuildCount(2* v+ 1,l,mid);
131     BuildCount(2*v +2,mid+1,r);
132     int repeat = 0;
133     int leftIndex = FindIndexInTree(v,tree[2*v+1].r);
134     int rightIndex = FindIndexInTree(v,tree[2*v+2].l);
135     if(tree[leftIndex].value == tree[rightIndex].value)
136     {
137         repeat = tree[2 * v +1].rCount + tree[2*v +2].lCount;
138     }
139     else
140     {
141         repeat = 0;
142     }
143     tree[v].maxCount = max( repeat,max( tree[2*v+1].maxCount, tree[2*v+2].maxCount) );
144     tree[v].lCount = tree[2*v+1].lCount;
145     if(tree[2*v + 1].lCount == mid - l + 1 && tree[leftIndex].value==tree[rightIndex].value)
146     {
147         tree[v].lCount += tree[2*v +2].lCount;
148     }
149     if(tree[2*v + 2].rCount == r- mid  && tree[rightIndex].value==tree[leftIndex].value)
150     {
151         tree[v].rCount += tree[2*v +1].rCount;
152     }
153 }
154 template
155 void IntervalTree::Add(int v,int l,int r,T m)//区间的更新操作
156 {
157     if(tree[v].l == l && tree[v].r == r)
158     {
159         tree[v].add +=m;
160         return ;
161     }
162     tree[v].value += m * (r- l +1);
163     int mid = (tree[v].l  + tree[v].r) /2;
164     if( r<= mid)
165     {
166         Add(v *2 +1,l,r,m);
167     }
168     else
169     {
170         if(l > mid)
171         {
172             Add(v *2 +2,l,r,m);
173         }
174         else
175         {
176             Add(v *2 +1,l,mid,m);
177             Add(v*2+2,mid+1,r,m);
178         }
179         
180     }
181     
182 }
183 template
184 T IntervalTree::Query(int v,int l,int r)//对根结点为v，查询区间l 到 r
185 {
186     if(tree[v].l == l && tree[v].r == r)
187     {
188         return tree[v].value +(tree[v].r - tree[v].l +1) * tree[v].add;
189     }
190     if(tree[v].add != 0)
191     {
192         tree[v].value += (tree[v].r - tree[v].l +1) * tree[v].add;
193         Add( v * 2 +1,tree[v].l,tree[v].Mid(),tree[v].add);
194         Add( v * 2 +2,tree[v].Mid()+1,tree[v].r,tree[v].add);
195         tree[v].add = 0;
196     }
197     int mid = tree[v].Mid();
198     if( r <= mid)
199     {
200         return     Query(v  * 2 +1,l,r);
201     }
202     else
203     {
204         if( l > mid)
205         {
206             return Query(v * 2+ 2,l ,r);
207         }
208         else
209         {
210             return Query(v * 2+1,l,mid) + Query(v* 2+2,mid+1,r);
211         }        
212     }
213 }
214 
215 template
216 void IntervalTree::Insert(int r,int i,T value)
217 {
218     if(tree[r].l == i && tree[r].r == i)
219     {
220         tree[r].value= value;
221         return ;
222     }
223     tree[r].value += value;
224     if(i <= tree[r].Mid())
225     {
226         Insert(2*r+1,i,value);
227     }
228     else
229     {
230         Insert(2 * r+ 2,i,value);
231     }
232 }
233 
234 int main()
235 {
236     int n = 0;
237     while(cin>>n && n > 0)
238     {
239         IntervalTree<int> it(n);
240         it.BuildTree(0,0,n-1);
241         int q = 0;
242         scanf("%d",&q);
243         for(int i = 0; i< n;i++)
244         {
245             int num = 0;
246             scanf("%d",&num);
247             it.Insert(0,i,num);
248         }
249         it.BuildCount(0,0,n-1);
250         for(int i =0 ;i < q;i++)
251         {
252             int x,y;
253             cin>>x>>y;
254             cout<0,x-1,y-1)<<endl;
255         }
256     }
257     return 0;
258 }

树形结构-线段树数据结构线段树 poj

POJ3368(Frequent values)--线段树

相关

数据结构--栈（C语言实现）

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

数据结构之二叉树

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

数据结构与算法之PHP排序算法（冒泡排序）

03java算法与数据结构------环形队列代码实现

Redis | 第一部分：数据结构与对象上篇《Redis设计与实现》

poj 2301（水题）

数据结构 -- 004.1 串的基本概念

标签