Thursday, 3 December 2015

**Painting the Boxes

Painting the Boxes 


Anup has N boxes. He painted them.
He wants to pick W adjacent boxes and give it to Suraj on his birthday. He wants all the W boxes he gifts to be of same colour. Anup repaints some of the boxes, and asks how many ways are there to gift W boxes to Suraj. Can you please help him out?

Input

  • The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a two integers N denoting the number of boxes and W denoting the number of adjacent boxes that he wants to gift Suraj. The second line contains N space-separated integers A1, A2, ..., AN denoting the initial colours of the boxes.
  • Third line of each test case contains a single integer Q, denoting the number of times Anup repainted a box. Q lines follow, each containing two integers Posi and Coli meaning that Posth box was repainted with colour Col.

Output

  • After each repainting query, output the number of ways Anup can gift Suraj W adjacent boxes of the same colour.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ W, Pos ≤ N
  • 1 ≤ Ai, Col ≤ 109
  • For 30 points : 1 ≤ Q ≤ 103, 1 ≤ N ≤ 104
  • For 70 points : 1 ≤ Q ≤ 104, 1 ≤ N ≤ 105

Example

Input:
1
4 2
1 1 1 1
3
1 1
1 2
2 2

Output:
3
2
2

Explanation

After the first repaint the boxes are coloured (1,1,1,1), which means 3 ways to choose 2 adjacent boxes of the same colour.
After the second repaint the boxes are coloured (2,1,1,1), which means 2 ways to select 2 adjacent boxes of the same colour.
After the third repaint thee boxes are coloured (2,2,1,1), which means 2 ways to select 2 adjacent boxes of the same colour.
--------------------------------------------------------------editorial----------------------------------------------------------------------------
above problem can be solved using Segment Tree, which would be much modular approach than handling many cases. HINT: For each node of segment tree stores length of color segment from left and length of color segment from right, color of left and right segment and ans for query for segment range. Update these values accordingly on each query operation.-
-------------------------------------------------------------------code------------------------------------------------------------------------
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli ;

lli arr[500010],lazy[500010];
 lli n;
   lli q,m;
long long int read_int(){
 char r;
 bool start=false,neg=false;
 long long int ret=0;
 while(true){
  r=getchar();
  if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
   continue;
  }
  if((r-'0'<0 || r-'0'>9) && r!='-' && start){
   break;
  }
  if(start)ret*=10;
  start=true;
  if(r=='-')neg=true;
  else ret+=r-'0';
 }
 if(!neg)
  return ret;
 else
  return -ret;
}

struct node 
 {
  lli pf,sf,pfc,sfc,ans;
  
 } seg[500001];
 
 lli ups,upe,qs,qe;//qs = query start index , qe= query end index   
 lli val;
 
 
 
 
 
 void build(lli index ,lli start,lli end)
  {
  // cout<<" build "<<start<<" "<<end<<endl;
   if(start==end)
    {
    // cout<<" leaf set"<<endl;
     seg[index].pf=arr[start];
     seg[index].sf=arr[start];
     if(m==1)
     seg[index].ans=1;
     else  seg[index].ans=0;
     seg[index].pfc=1;
     seg[index].sfc=1;
    }
    else if(start>end) return ;
    
    else
    {
   
     build(2*index,start,(start+end)/2);
     build(2*index+1,(start+end)/2+1,end);
     
    // cout<<"st "<<start<<" en "<<end<<endl;
     
     seg[index].pf=seg[2*index].pf;
     seg[index].sf=seg[2*index+1].sf;
     
      lli mid=(start+end)/2;
      lli ll=(mid-start+1);
      lli rr=(end-mid);
      if(seg[index].pf==seg[index].sf  && seg[2*index].pfc+seg[2*index+1].pfc==(end-start+1))
       {
     //   cout<<"entire set same "<<endl;
        seg[index].pfc=(end-start+1);
        seg[index].sfc=(end-start+1);
        if((end-start+1)-m>=0)
        seg[index].ans=(end-start+1)-m+1;
        else seg[index].ans=0;
       
  }
  
  else if(seg[2*index].sf!=seg[2*index+1].pf)
   {
    seg[index].pfc=seg[2*index].pfc;
               seg[index].sfc=seg[2*index+1].sfc;
    seg[index].ans=seg[2*index].ans+seg[2*index+1].ans;
}
  else
  {
  lli an=seg[2*index].ans+seg[2*index+1].ans;
  // cal for prefix;;;
  lli f=0;
      if(seg[2*index].pf==seg[2*index+1].pf  && ll==seg[2*index].pfc)
     {
      f=1;
     lli add=0;
     lli min=0;
     
  seg[index].pfc=ll+seg[2*index+1].pfc;
  if(seg[index].pfc-m>=0)
    add=seg[index].pfc-m+1;
    if(seg[2*index].pfc-m>=0) min=seg[2*index].pfc-m+1;
    if(seg[2*index+1].pfc-m>=0) min+=seg[2*index+1].pfc-m+1;
 
  an+=add-min;
}
else
{
seg[index].pfc=seg[2*index].pfc;
}
// cout<<"ans by pre "<<an<<endl;
/// //// cal for suffix::
if(seg[2*index].sf==seg[2*index+1].pf  && rr==seg[2*index+1].sfc)
     {
      f=1;
      lli add=0;
           lli min=0;
  seg[index].sfc=rr+seg[2*index].sfc;
  if(seg[index].sfc-m>=0)
  add=seg[index].sfc-m+1;
  if(seg[2*index+1].sfc-m>=0) min=seg[2*index+1].sfc-m+1;
  if(seg[2*index].sfc-m>=0) min+=seg[2*index].sfc-m+1;
  an+=add-min;
}
else
{
seg[index].sfc=seg[2*index+1].sfc;
}
// cout<<"ans by suf "<<an<<endl;
if(f==0)
{
if(seg[2*index].sf==seg[2*index+1].pf)
{
lli cc=seg[2*index].sfc+seg[2*index+1].pfc;
if(cc-m>=0) an+=cc-m+1;
if(seg[2*index].sfc-m>=0) an-=seg[2*index].sfc-m+1;
if(seg[2*index+1].pfc-m>=0) an-=seg[2*index+1].pfc-m+1;
}
}
// cout<<"ans by mid "<<an<<endl;
seg[index].ans=an;
  }
 // cout<<seg[index].pf<<" "<<seg[index].pfc<<" "<<seg[index].sf<<" "<<seg[index].sfc<<" "<<seg[index].ans<<endl;
    // 
    }
  }
  
  
  
  
   void update(lli index,lli start,lli end)
   {
   

   
   if(start>end || start>upe || end<ups) return ;// if(range in complitly out of range sooo need not to update ;;;;)
    if(start==end  && start==ups)
    {
    //cout<<" leaf set"<<"at "<<start<<endl;
     seg[index].pf=val;
     seg[index].sf=val;
     if(m==1)
     seg[index].ans=1;
     else  seg[index].ans=0;
     seg[index].pfc=1;
     seg[index].sfc=1;
     return;
    }
    
     update(2*index,start,(start+end)/2);
     update(2*index+1,((start+end)/2)+1,end);
  //    cout<<"update "<<start<<" "<<end<<endl;
     
    
     seg[index].pf=seg[2*index].pf;
     seg[index].sf=seg[2*index+1].sf;
     
      lli mid=(start+end)/2;
      lli ll=(mid-start+1);
      lli rr=(end-mid);
      
      if(seg[index].pf==seg[index].sf  && seg[2*index].pfc+seg[2*index+1].pfc==(end-start+1))
       {
     //   cout<<"entire range is same "<<endl;
        //cout<<"seg[index].pf"<<seg[index].pf<<"seg[index].sf"<<seg[index].sf<<endl;
        seg[index].pfc=(end-start+1);
        seg[index].sfc=(end-start+1);
        if((end-start+1)-m>=0)
        seg[index].ans=(end-start+1)-m+1;
        else seg[index].ans=0;
       
  }
   else if(seg[2*index].sf!=seg[2*index+1].pf)
   {
    seg[index].pfc=seg[2*index].pfc;
        seg[index].sfc=seg[2*index+1].sfc;
    seg[index].ans=seg[2*index].ans+seg[2*index+1].ans;
}
  else
  {
  lli an=seg[2*index].ans+seg[2*index+1].ans;
  // cal for prefix;;;
  lli f=0;
      if(seg[2*index].pf==seg[2*index+1].pf  && ll==seg[2*index].pfc)
     {
      f=1;
     lli add=0;
     lli min=0;
     
  seg[index].pfc=ll+seg[2*index+1].pfc;
  if(seg[index].pfc-m>=0)
    add=seg[index].pfc-m+1;
    if(seg[2*index].pfc-m>=0) min=seg[2*index].pfc-m+1;
    if(seg[2*index+1].pfc-m>=0) min+=seg[2*index+1].pfc-m+1;
 
  an+=add-min;
}
else
{
seg[index].pfc=seg[2*index].pfc;
}
// cout<<"ans by pre "<<an<<endl;
/// //// cal for suffix::
if(seg[2*index].sf==seg[2*index+1].pf  && rr==seg[2*index+1].sfc)
     {
      f=1;
      lli add=0;
           lli min=0;
  seg[index].sfc=rr+seg[2*index].sfc;
  if(seg[index].sfc-m>=0)
  add=seg[index].sfc-m+1;
  if(seg[2*index+1].sfc-m>=0) min=seg[2*index+1].sfc-m+1;
  if(seg[2*index].sfc-m>=0) min+=seg[2*index].sfc-m+1;
  an+=add-min;
}
else
{
seg[index].sfc=seg[2*index+1].sfc;
}
// cout<<"ans by suf "<<an<<endl;
if(f==0)
{
if(seg[2*index].sf==seg[2*index+1].pf)
{
lli cc=seg[2*index].sfc+seg[2*index+1].pfc;
if(cc-m>=0) an+=cc-m+1;
if(seg[2*index].sfc-m>=0) an-=seg[2*index].sfc-m+1;
if(seg[2*index+1].pfc-m>=0) an-=seg[2*index+1].pfc-m+1;
}
}
// cout<<"ans by mid "<<an<<endl;
seg[index].ans=an;
  }
//   cout<<seg[index].pf<<" "<<seg[index].pfc<<" "<<seg[index].sf<<" "<<seg[index].sfc<<" "<<seg[index].ans<<endl;
  
 }
 
 
 
 
 
 
 
 
 
 
   node  query(lli index ,lli start,lli end)
   {
     // cout<<" query "<<start<<" "<<end<<endl;
      if(start>end || start>qe || end<qs)
      {
    // cout<<" return dummy "<<endl;
       node inf;
      inf.pf=-999999999;
     inf.sf=-999999999;
     inf.pfc=0;
     inf.sfc=0;
       inf.ans=0;
       return inf;
       } 
      else if(qs<=start && qe>=end) 
       {
        
          return seg[index];    
      
          
       }
       
        
         node node1= query(2*index,start,(start+end)/2);
         node node2= query(2*index+1,(start+end)/2+1,end);
         node rnode;
         
          lli mid=(start+end)/2;
      lli ll=(mid-start+1);
      lli rr=(end-mid);
      if(rnode.pf==rnode.sf  && node1.pfc+node2.pfc==(end-start+1))
       {
        rnode.pfc=(end-start+1);
        rnode.sfc=(end-start+1);
        if((end-start+1)-m>=0)
        rnode.ans=(end-start+1)-m+1;
        else rnode.ans=0;
       
  }
   else if(node1.sf!=node2.pf)
   {
    rnode.pfc=node1.pfc;
    rnode.sfc=node2.sfc;
    rnode.ans=node1.ans+node2.ans;
}
 else
  {
  lli an=node1.ans+node2.ans;
  // cal for prefix;;;
  lli f=0;
      if(node1.pf==node2.pf  && ll==node1.pfc)
     {
      f=1;
     lli add=0;
     lli min=0;
     
  rnode.pfc=ll+node2.pfc;
  if(rnode.pfc-m>=0)
    add=rnode.pfc-m+1;
    if(node1.pfc-m>=0) min=node1.pfc-m+1;
    if(node2.pfc-m>=0) min+=node2.pfc-m+1;
 
  an+=add-min;
}
else
{
rnode.pfc=node1.pfc;
}
// cout<<"ans by pre "<<an<<endl;
/// //// cal for suffix::
if(node1.sf==node2.pf  && rr==node2.sfc)
     {
      f=1;
      lli add=0;
           lli min=0;
  rnode.sfc=rr+node1.sfc;
  if(rnode.sfc-m>=0)
  add=rnode.sfc-m+1;
  if(node2.sfc-m>=0) min=node2.sfc-m+1;
  if(node1.sfc-m>=0) min+=node1.sfc-m+1;
  an+=add-min;
}
else
{
rnode.sfc=node2.sfc;
}
// cout<<"ans by suf "<<an<<endl;
if(f==0)
{
if(node1.sf==node2.pf)
{
lli cc=node1.sfc+node2.pfc;
if(cc-m>=0) an+=cc-m+1;
if(node1.sfc-m>=0) an-=node1.sfc-m+1;
if(node2.pfc-m>=0) an-=node2.pfc-m+1;
}
}
// cout<<"ans by mid "<<an<<endl;
rnode.ans=an;
  }
 
  return rnode;
 
       
        
   }
   
   
int main()
 {
  lli t;
  cin>>t;
  while(t--)
  {
 
 
  
    cin>>n>>m;
    
    for(lli i=0;i<n;i++)arr[i]=read_int();
    build(1,0,n-1);
    cin>>q;
    
     while(q--)
      {
      lli x,y;
      cin>>x>>y;
       
      if(1)
{
 
ups=x-1;
upe=x-1;
val=y;
// for(lli i=ups;i<=upe;i++) arr[i]=val;
// cout<<"after update in the range "<<x-1<<" val "<<y<<endl;
 
update(1,0,n-1);
//cout<<"after update in the range "<<x-1<<" val "<<y<<endl;
 
}
     
       if(1)
        {
       
       
        qs=0;
        qe=n-1;
       
        node fin=query(1,0,n-1);
         cout<<fin.ans<<endl;
}
 }
}
      
 }
-------------------------------------------------------------------------------tester code------------------------------------------------------
#include <cassert>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 100000;

struct node {
 int l, r;
 int ok_pos, jump_next, jump_prev;
 int add_ok_pos, add_jump_next, add_jump_prev;
} tree[MAXN * 8];

int jump_next[MAXN], jump_prev[MAXN], w, Tn, n, Qn, color[MAXN], pos, new_color;

void init (int pos, int l, int r) {
 tree[pos].l = l;
 tree[pos].r = r;
 if (l < r) {
  init(pos + pos, l, (l + r) / 2);
  init(pos + pos + 1, (l + r) / 2 + 1, r); 
  tree[pos].ok_pos = tree[pos + pos].ok_pos + tree[pos + pos + 1].ok_pos;
  tree[pos].add_jump_next = tree[pos].add_ok_pos = tree[pos].add_jump_prev = -1;
 } else {
  tree[pos].ok_pos = ((jump_next[l] - l + 1) >= w);
  tree[pos].jump_next = jump_next[l];
  tree[pos].jump_prev = jump_prev[l];
  tree[pos].add_jump_next = tree[pos].add_ok_pos = tree[pos].add_jump_prev = -1;
 }
}

inline void update (int pos) {
 if (tree[pos].add_ok_pos != -1) {
  tree[pos].ok_pos = tree[pos].add_ok_pos * (tree[pos].r - tree[pos].l + 1);
  tree[pos + pos].add_ok_pos = tree[pos].add_ok_pos;
  tree[pos + pos + 1].add_ok_pos = tree[pos].add_ok_pos;
  tree[pos].add_ok_pos = -1;
 }
 if (tree[pos].add_jump_next != -1) {
  tree[pos].jump_next = tree[pos].add_jump_next;
  tree[pos + pos].add_jump_next = tree[pos].add_jump_next;
  tree[pos + pos + 1].add_jump_next = tree[pos].add_jump_next;
  tree[pos].add_jump_next = -1;  
 }
 if (tree[pos].add_jump_prev != -1) {
  tree[pos].jump_prev = tree[pos].add_jump_prev;
  tree[pos + pos].add_jump_prev = tree[pos].add_jump_prev;
  tree[pos + pos + 1].add_jump_prev = tree[pos].add_jump_prev;
  tree[pos].add_jump_prev = -1;
 }
}

void modify_ok_positions (int pos, int l, int r, int x) {
 update(pos);
 if (tree[pos].l == l && tree[pos].r == r) {
  tree[pos].ok_pos = x * (r - l + 1);
  tree[pos].add_ok_pos = x;
  return ;
 } else {
  if (l <= min(r, tree[pos + pos].r))
   modify_ok_positions(pos + pos, l, min(r, tree[pos + pos].r), x);
  if (max(l, tree[pos + pos + 1].l) <= r)
   modify_ok_positions(pos + pos + 1, max(l, tree[pos + pos + 1].l), r, x);
  update(pos + pos);
  update(pos + pos + 1);
  tree[pos].ok_pos = tree[pos + pos].ok_pos + tree[pos + pos + 1].ok_pos;
 }
}

void modify_jumps_next (int pos, int l, int r, int x) {
 update(pos);
 if (tree[pos].l == l && tree[pos].r == r) {
  tree[pos].jump_next = tree[pos].add_jump_next = x;
  return ;
 } else {
  if (l <= min(r, tree[pos + pos].r))
   modify_jumps_next(pos + pos, l, min(r, tree[pos + pos].r), x);
  if (max(l, tree[pos + pos + 1].l) <= r)
   modify_jumps_next(pos + pos + 1, max(l, tree[pos + pos + 1].l), r, x);
 }
}

void modify_jumps_prev (int pos, int l, int r, int x) {
 update(pos);
 if (tree[pos].l == l && tree[pos].r == r) {
  tree[pos].jump_prev = tree[pos].add_jump_prev = x;
  return ;
 } else {
  if (l <= min(r, tree[pos + pos].r))
   modify_jumps_prev(pos + pos, l, min(r, tree[pos + pos].r), x);
  if (max(l, tree[pos + pos + 1].l) <= r)
   modify_jumps_prev(pos + pos + 1, max(l, tree[pos + pos + 1].l), r, x);
 }
}

int get_jump_next (int pos, int j) {
 update(pos);
 if (tree[pos].l == tree[pos].r)
  return tree[pos].jump_next;
 if (tree[pos + pos].r >= j)
  return get_jump_next(pos + pos, j);
 else
  return get_jump_next(pos + pos + 1, j);
}

int get_jump_prev (int pos, int j) {
 update(pos);
 if (tree[pos].l == tree[pos].r)
  return tree[pos].jump_prev;
 if (tree[pos + pos].r >= j)
  return get_jump_prev(pos + pos, j);
 else
  return get_jump_prev(pos + pos + 1, j);
}

inline void update_bounds (int pos, bool change_answer) {
 int new_jump_next, new_jump_prev;
 if (pos == n)
  new_jump_next = n;
 else if (color[pos + 1] == color[pos]) 
  new_jump_next = get_jump_next(1, pos + 1);
 else
  new_jump_next = pos;
 
 if (pos == 1)
  new_jump_prev = 1;
 else if (color[pos - 1] == color[pos])
  new_jump_prev = get_jump_prev(1, pos - 1);
 else
  new_jump_prev = pos;
 
 modify_jumps_next(1, new_jump_prev, new_jump_next, new_jump_next);
 modify_jumps_prev(1, new_jump_prev, new_jump_next, new_jump_prev);
 
 if (change_answer && new_jump_next - new_jump_prev + 1 >= w) {
  modify_ok_positions(1, max(new_jump_prev, pos - w + 1), min(new_jump_next - w + 1, pos), 1);
 } 
}

int main (int argc, char * const argv[]) {
// freopen("input.txt", "r", stdin);
 ios_base::sync_with_stdio(false);
 cin >> Tn;
 assert(1 <= Tn && Tn <= 10);
 while (Tn--) {
  cin >> n >> w;
  assert(1 <= n && n <= 100000);
  assert(1 <= w && w <= n);
  for(int i = 1; i <= n; i++) {
   cin >> color[i];
   assert(1 <= color[i] && color[i] <= 1000000000);
  }
  for(int i = n; i >= 1; i--) {
   if (i == n || color[i] != color[i + 1])
    jump_next[i] = i;
   else
    jump_next[i] = jump_next[i + 1];
  }
  for(int i = 1; i <= n; i++) {
   if (i == 1 || color[i] != color[i - 1])
    jump_prev[i] = i;
   else
    jump_prev[i] = jump_prev[i - 1];
  }
  init(1, 1, n);
  cin >> Qn;
  assert(1 <= Qn && Qn <= 10000);
  while (Qn--) {
   cin >> pos >> new_color;
   assert(1 <= pos && pos <= n);
   assert(1 <= new_color && new_color <= 1000000000);
   if (color[pos] == new_color) {
    cout << tree[1].ok_pos << endl;
    continue;
   }
   
   color[pos] = new_color;
   modify_ok_positions(1, max(1, pos - w + 1), pos, 0);
   update_bounds(pos, true);   
   if (pos > 1)
    update_bounds(pos - 1, false);
   if (pos < n)
    update_bounds(pos + 1, false);
   
         
   cout << tree[1].ok_pos << endl;
   
  }
 }
    return 0;
}
    Posted by at

    No comments:

    Post a Comment

    Subscribe to: Post Comments (Atom)