D. Interesting ArraY
We'll call an array of n non-negative integers a[1], a[2], ..., a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value 
should be equal to qi.
should be equal to qi.
Your task is to find any interesting array of n elements or state that such array doesn't exist.
Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".
Input
The first line contains two integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of elements in the array and the number of limits.
Each of the next m lines contains three integers li, ri, qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230) describing the i-th limit.
Output
If the interesting array exists, in the first line print "YES" (without the quotes) and in the second line print n integers a[1], a[2], ..., a[n](0 ≤ a[i] < 230) decribing the interesting array. If there are multiple answers, print any of them.
If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.
Examples
input
3 1 1 3 3
output
YES 3 3 3
input
3 2 1 3 3 1 3 2
output
NO
initially i write a code in which segtree is of seg[10^5][31] for each bit i build a segment tree but
it gives tle so we have to do it in the seg[10^5]
first of all let us discuss first (TLE) approach
if for a query l , r, val
all if the ith bit of val is 1 than all number in the range from l to r must have ith bit on ,and if ith bit of val is off than atleast 1 bit of all the numbers in the range l to r must be off,
so what i did is make ith bit value of seg[L][i] to seg[R][i] with value 1 it is a type of range sum update means now (seg[R][i]-seg[L][i]=R-L+1) , and do not do any thing for the off bit ,,,
now first of all we have to check whether ans is yes or not
for each update range do this ,
for all bits (0 ,31 )
if ith bit of val is on than range sum of seg[L][i] to seg[R][i] must be equal to R-L+1,
if ith bit of val is off than range sum of seg[L][i] to seg[R][i] must be less to R-L+1(atleast 1 bit in this range must be off )
if ans is yes than we can easily compute value at at all index ,
just do query for all bits of the ith number and form the number ...
but this approach gives TLE see this code for clarity
ll
m-----------------------------------------------------TLE CODE----------------------------------------------
#include<bits/stdc++.h> using namespace std; typedef long long int lli; int ma[500000][32]; vector<pair<pair<int,int>,lli> > v; lli seg[500000][32]; #define inf 100000001 lli ans[500000]; long long int qry(int index,int start,int end,int qs,int qe,int bit) { if(start>end || end<qs || start>qe) { return 0; } if(start>=qs && end<=qe) { return seg[index][bit]; } long long int q1=qry(2*index,start,(start+end)/2,qs,qe,bit); long long int q2=qry(2*index+1,((start+end)/2)+1,end,qs,qe,bit); return q1+q2; } void build(int index,int start,int end,int bit) { if(start>end) return ; if(start==end) { if(ma[start][bit]>=1) seg[index][bit]=1; else seg[index][bit]=0; return ; } build(2*index,start,(start+end)/2,bit); build(2*index+1,((start+end)/2)+1,end,bit); seg[index][bit]=seg[2*index][bit]+seg[2*index+1][bit]; } int main() { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<m;i++) { int l,r; lli va; scanf("%d %d %lld",&l,&r,&va); v.push_back(make_pair(make_pair(l,r),va)); for(int j=0;j<=31;j++) { if(va & (1<<j)) { // cout<<j<<" bit on "<<endl; ma[l][j]++; ma[r+1][j]--; } } } for(int j=0;j<=31;j++) { for(int i=1;i<=n;i++) { ma[i][j]+=ma[i-1][j]; } } /* for(int j=0;j<=3;j++) { for(int i=1;i<=n;i++) { cout<<ma[i][j]<<" "; } cout<<endl; }*/ for(int i=0;i<=31;i++) { build(1,1,n,i); } int f=0; for(int i=0;i<m;i++) { int l,r; lli val; l=v[i].first.first; r=v[i].first.second; val=v[i].second; // cout<<l<<" "<<r<<" "<<val<<endl; for(int j=0;j<=31;j++) { lli count=qry(1,1,n,l,r,j); // cout<<" bit "<<j<<" count "<<count<<endl; if(((val & (1<<j) ) && count <r-l+1) ||(!(val & (1<<j) ) && count ==r-l+1)) { // cout<<"set flag on "<<endl; f=1; break; } if(f==1) break; } } if(f==1) { cout<<"NO"<<endl; return 0; } else { cout<<"YES"<<endl; for(int i=1;i<=n;i++) { // cout<<" val for index "<<i<<endl; lli vv=0; for(int j=0;j<=31;j++) { int sum=ma[i][j]; // cout<<" bit "<<j<<" count "<<sum<<endl; if(sum>=1) vv=vv|(1<<j); } ans[i]=vv; } for(int i=1;i<=n;i++) printf("%lld ",ans[i]); } }-----------------------------------------------NOW COME TO AC APPROACH -------------------------------
instead of update each bit separately , what we can do that form all query generate number
this can be done easily ,
let decide each bit value of all number 1 by one ( from bit 0 to 30 ),
if in any query ith bit of jth number is on meas ith bit of jth number is 1 for sure ,
now use this approach to generate all (1 to n ) numbers
// generating all numbers in each step we decide ith bit of all numbers 1 to n
for(int i=0;i<=30;i++)
{
for(int k=0;k<=n;k++) ma[k]=0;
for(int j=0;j<m;j++)// all m queries
{
int l=v[j].first.first;// details from the query
int r=v[j].first.second;// details from the query
lli val=v[j].second;// details from the query
if(val & (1<<i))// means all number from L to R have ith bit on
{
ma[l]++;
ma[r+1]--;
}
}
for(int k=1;k<=n;k++)// making forward array and checking it ma[k]>1 means //ith bit of kth number is onby this query
{
ma[k]+=ma[k-1];
if(ma[k]>=1) ans[k]=ans[k] | (1<<i);
}
}
now after this we have to check whether ans is yes of no
for this first we build a seg tree which contans and off all L,R according to our generated array
easy do implement this
void build(int index,int start,int end)
{
if(start>end) return ;
if(start==end)
{
seg[index]=ans[start];
return ;
}
build(2*index,start,(start+end)/2);
build(2*index+1,((start+end)/2)+1,end);
seg[index]=seg[2*index] & seg[2*index+1];
}
now we have to check wether ans is yes or no , now we can easily do this with our seg tree
check all query from 1 to m
and if for any query and of L to R is not equal to val than ans is no
for(int i=0;i<m;i++)
{
int l,r;
lli val;
l=v[i].first.first;
r=v[i].first.second;
val=v[i].second;
lli aa=qry(1,1,n,l,r);
if(aa!=val)
{
f=1;
break;
}
}
lli qry(int index,int start,int end,int qs,int qe)
{
if(start>end || end<qs || start>qe)
{
return all;
}
if(start>=qs && end<=qe)
{
return seg[index];
}
lli q1=qry(2*index,start,(start+end)/2,qs,qe);
lli q2=qry(2*index+1,((start+end)/2)+1,end,qs,qe);
return q1 & q2;
}
if ans is yes than
just print generated ans[] array
-------------------------------------------------------or------------------------------------------------------
We will solve the task for every distinct bit. Now we must handle new constraint: l[i], r[i], q[i]. If number q[i] has 1 in bit with numberpos, then all numbers in segment [l[i], r[i]] will have 1 in that bit too. To do that, we can use a standard idea of adding on a segment.
Let's do two adding operation in s[pos] array — in position l[i] we will add 1, and in posiotion r[i] + 1 — -1. Then we will calculate partial sums of array s[pos], and if s[pos][i] > 0 (the sum on prefix length i + 1), then bit at position pos will be 1, otherwise — 0.
After that, you can use segment tree to check satisfying constraints.
--------------------------------------------------------------------------------------------------------------------CODE
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int ma[500000];
vector<pair<pair<int,int>,lli> > v;
lli seg[500000];
#define inf 100000001
lli ans[500000];
lli all=0;
lli qry(int index,int start,int end,int qs,int qe)
{
if(start>end || end<qs || start>qe)
{
return all;
}
if(start>=qs && end<=qe)
{
return seg[index];
}
lli q1=qry(2*index,start,(start+end)/2,qs,qe);
lli q2=qry(2*index+1,((start+end)/2)+1,end,qs,qe);
return q1 & q2;
}
void build(int index,int start,int end)
{
if(start>end) return ;
if(start==end)
{
seg[index]=ans[start];
return ;
}
build(2*index,start,(start+end)/2);
build(2*index+1,((start+end)/2)+1,end);
seg[index]=seg[2*index] & seg[2*index+1];
}
int main()
{
all=0;
for(int i=0;i<=30;i++) all=all|(1<<i);
//cout<<all<<endl;
int n,m;
scanf("%d %d", &n, &m);
for(int i=0;i<=4*n;i++)seg[i]=all;
for(int i=0;i<m;i++)
{
int l,r;
lli va;
scanf("%d %d %lld",&l,&r,&va);
v.push_back(make_pair(make_pair(l,r),va));
}
for(int i=0;i<=30;i++)
{
for(int k=0;k<=n;k++) ma[k]=0;
for(int j=0;j<m;j++)
{
int l=v[j].first.first;
int r=v[j].first.second;
lli val=v[j].second;
if(val & (1<<i))
{
// cout<<i<<" bit on "<<" of q "<<endl;;
ma[l]++;
ma[r+1]--;
}
}
for(int k=1;k<=n;k++)
{
ma[k]+=ma[k-1];
if(ma[k]>=1) ans[k]=ans[k] | (1<<i);
// cout<<ans[k]<<" ";
// ma[k]=0;
}
}
// for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
build(1,1,n);
int f=0;
for(int i=0;i<m;i++)
{
int l,r;
lli val;
l=v[i].first.first;
r=v[i].first.second;
val=v[i].second;
lli aa=qry(1,1,n,l,r);
if(aa!=val)
{
f=1;
break;
}
}
if(f==1)
{
cout<<"NO"<<endl;
return 0;
}
else
{
cout<<"YES"<<endl;
for(int i=1;i<=n;i++)
{
printf("%lld ",ans[i]);
}
}
}
No comments:
Post a Comment