# UVA 11235 সমস্যাটি সমাধানের প্রক্রিয়া কেমন হওয়া উচিৎ?

 1 বুঝতে পারছি এটাতে সেগমেন্ট ট্রি ব্যবহার করতে হবে এবং ফ্রিকোয়েন্সি বা cout এর একটা অ্যারে থাকবে। এরপরে আটকে যাচ্ছি। সমস্যার লিঙ্ক asked 03 Apr '18, 09:39 Shaeekh 86●12 Mosharraf Hosain ♦ 1.1k●1●8

 2 You can solve this problem using segment tree. If you don't know about segment tree, you may learn it from here or search on google. Let node[] is an array which stores the information of each node of the segment tree. Each node will store five information in the range which it covers: left most value in the range(let it be lVal) right most value in the range(let it be rVal) frequency of left most value(let it be lCnt) frequency of right most value(let it be rCnt) maximum frequency of value in the range(let it be mxCnt) First the tree building part: When you build the tree, for the leaf node(i.e. node which covers a single index of array), the left most and right most both value will be the value of that index and all the remaining three information(i.e. 3rd, 4th and 5th information above) will be 1. When you are at any other node which is not a leaf, you have to merge the left and right node to store the information at this node: Let you are at node cur and L is the left node and R is the right node of this node. Then, node[cur].lVal = node[L].lVal node[cur].rVal = node[R].lVal node[cur].lCnt = node[L].lCnt node[cur].rCnt = node[R].lCnt node[cur].mxCnt = max(node[L].mxCnt, node[R].mxCnt) Now check whether node[L]rVal and node[R].lVal is equal or not. If node[L].rVal equals to node[R].lVal then: node[cur].mxCnt = max(node[cur].mxCnt, node[L].rCnt+node[R].lCnt) if node[L].lVal equals to node[L].rVal, then add node[R].lCnt to node[cur].lCnt if node[R].lVal equals to node[R].rVal, then add node[L].rCnt to node[cur].rCnt Now the query part: If you are at any node which is outside the range that we are query for then: return -1 If you are at such node whose range is fully inside the range that we are query for, then: return node[cur].mxCnt Otherwise recursively find the answer for the node L and node R then merge them to find the actual answer for this node as follows: Let qL and qR be the answer for the node L and R, respectively. Our answer is(for now) maximum of these two values, i.e. ans = max(qL, qR) Now, check whether node[L].rVal equals to node[R].lVal or not. If node[L].rVal equals to node[R].lVal then: ans = max(ans, frequency of node[L].rVal + frequency of node[R].lVal) Finally, if you are stuck to implement the solution, here is my accepted solution in c++. answered 04 Apr '18, 09:55 shahidul_brur 31●3 1 @shahidul_brur, প্রশ্ন/উত্তর অবশ্যই বাংলায় হতে হবে। সময় করে উত্তরটি বাংলায় রূপান্তর করে দিন। (04 Apr '18, 14:13) Mosharraf Hosain ♦
 toggle preview community wiki:

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Question tags:

×139
×55
×38
×18
×14

question asked: 03 Apr '18, 09:39

question was seen: 1,452 times

last updated: 04 Apr '18, 17:53