Some Segment Tree problems
algorithms
imported
UVA 11235 just do a normal range search on frequency table. Here is the code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ori,freq;
int N,Q,t;
//#define DEBUG
#include <fstream>
#ifdef DEBUG
ifstream fin("uva11235.in");
ofstream fout("uva11235.out");
#endif
void redirect(){
#ifdef DEBUG
std::streambuf *cinbuf = std::cin.rdbuf();
std::cin.rdbuf(fin.rdbuf());
std::streambuf *coutbuf = std::cout.rdbuf();
std::cout.rdbuf(fout.rdbuf());
#endif
}
class SegmentTree{
private:
int st[800001];
int left(int p){return p<<1;}
int right(int p){return (p<<1)+1;};
void build(int p,int L,int R){
if(L==R){
st[p]=L;
}
else{
build(left(p),L,(L+R)/2);
build(right(p),(L+R)/2+1,R);
int l=st[left(p)];
int r=st[right(p)];
st[p]=(freq[l]<=freq[r])?r:l;
}
}
int rmq(int p,int L,int R,int i,int j){
if(i>R||j<L)
return -1;
if(i<=L&&R<=j){
return st[p];
}
int l=rmq(left(p),L,(L+R)/2,i,j);
int r=rmq(right(p),(L+R)/2+1,R,i,j);
if(l==-1)return r;
if(r==-1)return l;
return (freq[l]<=freq[r])?r:l;
}
bool checkBoundary(int targetPos,int result,bool left){
if(left){
if(targetPos-1>=0)
return ori[targetPos-1]!=result;
else
return false;
}
else{
if(targetPos+1<freq.size())
return ori[targetPos+1]!=result;
else
return false;
}
}
public:
void buildTree(){
build(1,0,freq.size()-1);
}
int query(int left,int right){
if(left==right)
return 1;
int pos=rmq(1,0,freq.size()-1,left,right);
int k=freq[pos];
int leftCount=0;
int rightCount=0;
if(!checkBoundary(left,ori[pos],true)){
for(int i=left;i<=right;i++){
if(ori[i]!=ori[pos]){
break;
}
else{
leftCount++;
}
}
}
if(!checkBoundary(right,ori[pos],false)){
for(int i=right;i>=left;i--){
if(ori[i]!=ori[pos]){
break;
}
else{
rightCount++;
}
}
}
if(leftCount&&rightCount){
return right-left+1;
}
else if(leftCount&&!rightCount){
if(leftCount==right-left+1)
return leftCount;
return max(leftCount,query(left+leftCount,right));
}
else if(!leftCount&&rightCount){
if(rightCount==right-left+1)
return rightCount;
return max(query(left,right-rightCount),rightCount);
}
else{
return k;
}
}
};
SegmentTree st;
int a,b;
void pushToFreq(int frequence){
for(int i=0;i<frequence;i++)
freq.push_back(frequence);
}
void translateToFreq(){
int last=0;
int count=0;
bool first=true;
for(int i=0;i<ori.size();i++){
if(first){
last=ori[i];
count=1;
first=false;
continue;
}
if(last==ori[i]){
count++;
}
else{
pushToFreq(count);
last=ori[i];
count=1;
}
}
pushToFreq(count);
}
int main(){
redirect();
while(cin>>N){
if(!N)
break;
cin>>Q;
ori.clear();
freq.clear();
for(int i=0;i<N;i++){
cin>>t;
ori.push_back(t);
}
translateToFreq();
st.buildTree();
for(int j=0;j<Q;j++){
cin>>a>>b;
cout<<st.query(a-1,b-1)<<endl;
}
}
return 0;
}UVA 11402 This problem is quite tricky, if you write an unoptimized segment tree, you will definitely get TLE. The trick is that we need to use lazy-update for the segment tree.
#include <iostream>
#include <string>
#include <vector>
#define SET 1
#define CLEAR 2
#define FLIP 3
using namespace std;
//#define DEBUG
#include <fstream>
#ifdef DEBUG
ifstream fin("uva11402.in");
ofstream fout("uva11402.out");
#endif
void redirect(){
#ifdef DEBUG
std::streambuf *cinbuf = std::cin.rdbuf();
std::cin.rdbuf(fin.rdbuf());
std::streambuf *coutbuf = std::cout.rdbuf();
std::cout.rdbuf(fout.rdbuf());
#endif
}
bool pirates[40960010];
int U[4096001];
int position[10240000];
int N;
vector<int> changeList;
class SegmentTree{
private:
int st[4096001];
int left(int p){return p<<1;}
int right(int p){return (p<<1)+1;};
void build(int p,int L,int R){
U[p]=0;
if(L==R){
st[p]=pirates[L];
}
else{
build(left(p),L,(L+R)/2);
build(right(p),(L+R)/2+1,R);
int l=st[left(p)];
int r=st[right(p)];
st[p]=l+r;
}
}
int rmq(int p,int L,int R,int i,int j){
if(i>R||j<L)
return -1;
propagate(p,L,R);
if(i<=L&&R<=j){
return st[p];
}
int l=rmq(left(p),L,(L+R)/2,i,j);
int r=rmq(right(p),(L+R)/2+1,R,i,j);
if(l==-1)return r;
if(r==-1)return l;
return l+r;
}
int flip(int sign){
if(sign==SET)
return CLEAR;
if(sign==CLEAR)
return SET;
if(sign==FLIP)
return 0;
if(sign==0)
return FLIP;
}
void propagate(int p,int L,int R){
if(U[p]==SET){
st[p]=R-L+1;
if(L!=R){
U[left(p)]=SET;
U[right(p)]=SET;
}
}
else if(U[p]==CLEAR){
st[p]=0;
if(L!=R){
U[left(p)]=CLEAR;
U[right(p)]=CLEAR;
}
}
else if(U[p]==FLIP){
st[p]=R-L+1-st[p];
if(L!=R){
U[left(p)]=flip(U[left(p)]);
U[right(p)]=flip(U[right(p)]);
}
}
U[p]=0;
}
public:
void rangeSet(int p,int L,int R,int i,int j){
propagate(p,L,R);
if(R<i||L>j)
return;
if(L==R){
st[p]=1;
return;
}
if(i<=L&&R<=j){
st[p]=R-L+1;
U[left(p)]=SET;
U[right(p)]=SET;
return;
}
rangeSet(left(p),L,(L+R)/2,i,j);
rangeSet(right(p),(L+R)/2+1,R,i,j);
st[p]=st[left(p)]+st[right(p)];
}
void rangeClear(int p,int L,int R,int i,int j){
propagate(p,L,R);
if(R<i||L>j)
return;
if(L==R){
st[p]=0;
U[p]=0;
return;
}
if(i<=L&&R<=j){
st[p]=0;
U[left(p)]=CLEAR;
U[right(p)]=CLEAR;
return;
}
rangeClear(left(p),L,(L+R)/2,i,j);
rangeClear(right(p),(L+R)/2+1,R,i,j);
st[p]=st[left(p)]+st[right(p)];
}
void rangeFlip(int p,int L,int R,int i,int j){
propagate(p,L,R);
if(R<i||L>j)
return;
if(L==R){
st[p]=(st[p]==1)?0:1;
return;
}
if(i<=L&&R<=j){
st[p]=R-L+1-st[p];
U[left(p)]=flip(U[left(p)]);
U[right(p)]=flip(U[right(p)]);
return;
}
rangeFlip(left(p),L,(L+R)/2,i,j);
rangeFlip(right(p),(L+R)/2+1,R,i,j);
st[p]=st[left(p)]+st[right(p)];
}
void buildTree(){
build(1,0,N-1);
}
int query(int left,int right){
return rmq(1,0,N-1,left,right);
}
};
SegmentTree st;
int T,P,M,a,b;
char ch;
string s;
void concatenate(int n,string s){
for(int i=0;i<n;i++)
for(int j=0;j<s.size();j++){
N++;
pirates[N]=(s[j]=='1');
}
}
void toBuccaneer(int left,int right){
//for(int i=left;i<=right;i++){
//if(!pirates[i])
// changeList.push_back(i);
//pirates[i]=true;
//}
st.rangeSet(1,0,N-1,left,right);
}
void toBarbary(int left,int right){
//for(int i=left;i<=right;i++){
//if(pirates[i])
// changeList.push_back(i);
//pirates[i]=false;
//}
st.rangeClear(1,0,N-1,left,right);
}
void inverse(int left,int right){
//for(int i=left;i<=right;i++){
//changeList.push_back(i);
// pirates[i]=1-pirates[i];
//}
st.rangeFlip(1,0,N-1,left,right);
}
int main(){
redirect();
cin>>T;
for(int t=0;t<T;t++){
N=-1;
cout<<"Case "<<t+1<<":"<<endl;
cin>>P;
for(int i=0;i<P;i++){
cin>>a>>s;
concatenate(a,s);
}
N++;
st.buildTree();
cin>>M;
int counter=0;
for(int i=0;i<M;i++){
cin>>ch>>a>>b;
if(ch=='F')
toBuccaneer(a,b);
else if(ch=='E')
toBarbary(a,b);
else if(ch=='I')
inverse(a,b);
else{
counter++;
cout<<"Q"<<counter<<": "<<st.query(a,b)<<endl;
}
}
}
return 0;
}UVA 12532 easy problem, an optimized segment tree is enough to pass it.
#include <iostream>
using namespace std;
#define INFINITY 2147483647
//#define DEBUG
#include <fstream>
#ifdef DEBUG
ifstream fin("uva12532.in");
ofstream fout("uva12532.out");
#endif
void redirect(){
#ifdef DEBUG
std::streambuf *cinbuf = std::cin.rdbuf();
std::cin.rdbuf(fin.rdbuf());
std::streambuf *coutbuf = std::cout.rdbuf();
std::cout.rdbuf(fout.rdbuf());
#endif
}
int v[100000];
int N,K,a,b;
char ch;
class SegmentTree{
private:
short st[400001];
int left(int p){return p<<1;}
int right(int p){return (p<<1)+1;};
void build(int p,int L,int R){
if(L==R){
if(v[L]>0)
st[p]=1;
else if(v[L]<0)
st[p]=-1;
else
st[p]=0;
}
else{
build(left(p),L,(L+R)/2);
build(right(p),(L+R)/2+1,R);
int l=st[left(p)];
int r=st[right(p)];
st[p]=l*r;
}
}
int rmq(int p,int L,int R,int i,int j){
if(i>R||j<L)
return -INFINITY;
if(i<=L&&R<=j){
return st[p];
}
int l=rmq(left(p),L,(L+R)/2,i,j);
int r=rmq(right(p),(L+R)/2+1,R,i,j);
if(l==-INFINITY)return r;
if(r==-INFINITY)return l;
return l*r;
}
public:
char query(int i,int j){
int k=rmq(1,0,N-1,i,j);
if(k>0)
return '+';
else if(k<0)
return '-';
else
return '0';
}
void update(int p,int L,int R,int i){
if(!(L<=i&&i<=R))
return;
if(L==R){
if(v[L]>0)
st[p]=1;
else if(v[L]<0)
st[p]=-1;
else
st[p]=0;
return;
}
update(left(p),L,(L+R)/2,i);
update(right(p),(L+R)/2+1,R,i);
st[p]=st[left(p)]*st[right(p)];
}
void buildTree(){
build(1,0,N-1);
}
};
SegmentTree st;
int main(){
redirect();
while(cin>>N>>K){
for(int i=0;i<N;i++)
cin>>v[i];
st.buildTree();
for(int i=0;i<K;i++){
cin>>ch>>a>>b;
if(ch=='C'){
v[a-1]=b;
st.update(1,0,N-1,a-1);
}
else{
cout<<st.query(a-1,b-1);
}
}
cout<<endl;
}
return 0;
}