Question : “Distinct Dishting | Toph”
My solution : “rhQRQI - Online C++0x Compiler & Debugging Tool - Ideone.com”
I m trying this question since from last night , first I don’t know MO + update , so I learn from various resources , then I implement above code , please help me , this code gives me TLE , please help
@galencolin @carre @rahulmysuru7 @everule1 @humane @ssjgz(can u please check this code give me tle due to algo or something else ? )
The implementation looks fine, there might be some issue with comparator.
Really u read my whole code very fast , and see with update I can’t use more faster method , I know if it doesn’t have any update query then I will write more efficient comparator , but there is some other issue .
@ssrivastava990 I think you had misfigured the actual techniques. This is question of square root decomposition IMO. As there is update you can’t use MO . Mo is only useful when there is no update statement. And due to this reason this question is giving you a TLE. That’s what I think. Please rectify my mistake if i have done any.
Lol , then u have to read some blogs , let me give u some links -
Not possible as far as this question is concerned either u solve with 2-D interval tree or some other thing , but with simple SQRT decomposition not possible and if possible tell me apporach and I will try.
Right bro i miss something . As we need unique element hence square root will not a best solution. Sorry for my bad idea.
I saw 2nd post. In one of them has wrote that it’s mostly impossible update query with Mo but it may possible at the cost of more complexity. It may be one of reason of TLE of you have tried something fancy like more block size or anything.
No the solutions which passes also use same algo u can see 4 solutions .
while (cr_time < qt)
{
updo(cr_time);
cr_time++;
}
while (cr_time > qt)
{
cr_time--;
undo(cr_time);
}
What these lines are doing?
these lines doing undo and updo operations , undo means undo all update queries , and updo means do all update queries.
why not segment tree? Each node stores the result for its corresponding interval and the list of distint multiples of 3 in the interval
@carre please read this “Update query on Mo's Algorithm - Codeforces” , if this is possible via segment tree then already posted solution , but that’s not the case.
ok, I see. If I correctly understand from your code in each block you are making all updates but you can avoid that and makes only updates that corresponds to that block. To do that you need to organize updates by block. Sorry if my attemps are not useful, I’m just thinking laudly, I can try in a couple of hours when finish my work 
ok, finally accepted with some modifications to your code
/*
Author : Chandan Agrawal
College : Poornima College of Engg. jaipur, Raj
Mail : chandanagrawal23@gmail.com
" when you are not practicing someone else is ,
and the day u meet them u will lose "
*/
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 100050
#define ll long long
#define ld long double
#define lli int
#define pb push_back
#define INF 1000000000000
#define mod 1000000007
// trignometric function always give value in Radians only
#define PI acos(-1) //3.1415926535897932384626433832795028
#define dsin(degree) sin(degree*(PI/180.0))
#define dcos(degree) cos(degree*(PI/180.0))
#define dtan(degree) tan(degree*(PI/180.0))
#define rsin(radian) sin(radian)
#define rcos(radian) cos(radian)
#define rtan(radian) tan(radian)
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define memf(a) memset(a,false,sizeof(a))
#define loop(i,n) for (lli i = 0; i < n; i++)
#define FOR(i,a,b) for (lli i = a; i < b; i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
#define sz(x) int(x.size())
#define F first
#define S second
#define mii map<lli,lli>
#define pii pair<lli,lli>
#define vi vector<lli>
#define vvi vector<vi>
#define vpi vector<pii>
#define vbool vector<bool>
#define seti set<lli>
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a/gcd(a,b))*b
#define abs(x) ((x < 0)?-(x):x)
#define endl '\n'
template <typename Head>
void print(Head&& head)
{
cout<<head<<endl;
}
template <typename Head, typename... Tail>
void print(Head&& head, Tail... tail)
{
cout<<head<<" ";
print(tail...);
}
#define scanarr(a,n) for(lli i=0;i<n;i++) cin>>a[i];
#define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
#define printarr(a,n) for(lli i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
#define printvec(vec) for(auto xt : vec) cout<<xt<<" "; cout<<"\n";
#define FD(N) fixed<<setprecision(N)
#define deb(x) cout<<#x<<" "<<x<<endl;
/*
1D vector - vi dp(n,value);
2D vector - vvi dp(n,vi(n,value));
*/
// chandan1,2
void chandan1(){int y=1;return;}
void chandan2(){
loop(i,10){
lli x=1;
}
return(chandan1());
}
//-------------------------------------------------MO's ALGO (with update) ---------------------------------------------------------------
const int blk_sz = 2150; // u can take sqrt(n) too
typedef struct query
{
lli l , r , q_time , id;
query(lli L , lli R , lli Q_time , lli ID)
{
l = L;
r = R;
q_time = Q_time;
id = ID;
}
}query;
typedef struct update
{
lli ind , prev_val , new_val;
update(lli Ind , lli Prev_val , lli New_val)
{
ind = Ind;
prev_val = Prev_val;
new_val = New_val;
}
}update;
bool cmp(query a , query b)
{
lli blk_num_a_l = a.l / blk_sz;
lli blk_num_b_l = b.l / blk_sz;
if(blk_num_a_l != blk_num_b_l)
return(blk_num_a_l < blk_num_b_l);
lli blk_num_a_r = a.r / blk_sz;
lli blk_num_b_r = b.r / blk_sz;
if(blk_num_a_r != blk_num_b_r)
return(blk_num_a_r < blk_num_b_r);
return(a.q_time < b.q_time);
}
lli a[MAX] , cnt=0 ;
ll total = 0;
unordered_map<lli,lli> freq;
vector<query> q;
vector<update> upd;
void add(lli pos)
{
if (a[pos]==0) return;
freq[a[pos]]++;
if(freq[a[pos]] == 1)
total += a[pos];
}
void remove(lli pos)
{
if (a[pos]==0) return;
freq[a[pos]]--;
if(freq[a[pos]] == 0)
total -= a[pos];
}
//------------------------------------------------- MO's ALGO (with update) ---------------------------------------------------------------
lli ML = 0 , MR = -1;
void updo(lli pos)
{
lli new_val = upd[pos].new_val;
lli index = upd[pos].ind;
if((index >= ML) and (index <= MR) ) remove(index);
a[index] = new_val;
if((index >= ML) and (index <= MR) ) add(index);
}
void undo(lli pos)
{
lli prev_val = upd[pos].prev_val;
lli index = upd[pos].ind;
if((index >= ML) and (index <= MR) ) remove(index);
a[index] = prev_val;
if((index >= ML) and (index <= MR) ) add(index);
}
int main(){
fastio
lli t=1;
//cin>>t;
chandan2();
while(t--) {
lli n,m;
cin>>n>>m;
loop(i,n) {
cin >> a[i];
if (a[i] % 3 != 0) a[i] = 0;
}
vector<int> prev(n);
for(int i=0;i<n;++i) prev[i]=a[i];
lli updates = 0;
loop(i,m)
{
lli type;
cin>>type;
if(type == 0) //update query
{
lli ind , val;
cin>>ind>>val;
if (val%3!=0) val=0;
ind--;
updates++;
upd.pb({ind , prev[ind] , val}); //index , prev_val , new_val;
prev[ind]=val;
}
else // ask query
{
lli l , r;
cin>>l>>r;
--l,--r;
q.pb({l,r,updates,i});
}
}
sort(all(q),cmp);
ll ans[m];
mem1(ans);
lli cr_time = 0;
for(auto xt : q)
{
lli l =xt.l;
lli r = xt.r;
lli qt = xt.q_time; // how many updates till this query ?
lli id = xt.id;
// print(l,r,qt,id);
while(cr_time < qt)
{
updo(cr_time);
cr_time++;
}
while(cr_time > qt)
{
cr_time--;
undo(cr_time);
}
// STANDARD MO -
while(MR < r)
{
MR++;
add(MR);
}
while(ML > l)
{
ML--;
add(ML);
}
while(MR > r)
{
remove(MR);
MR--;
}
while(ML < l)
{
remove(ML);
ML++;
}
ans[id] = total;
}
loop(i,m)
{
if(ans[i]!= -1)
print(ans[i]);
}
}
return 0;
}
I’ve learned something, I would never had use MO with updates
Thank you very much , also I think the main issue is I m not taking prev array , although in my copy I wrote same thing like u just copy the array into prev array and change the value( when update query comes) in prev array, but forgot to write in code, ,thanks, also of I take blk_sz 700 is it give TLE Or AC…
Let me try , thanks once again.