Lexical Sign Sequence

Topic link
greedy + Tree array

The main idea of the topic ： Construct a signal sequence with the smallest lexicographic order （ It only includes 1,-1） bring k The sum of the specified intervals is greater than or equal to the given value .

Ideas ： You can start by letting all empty All the parts become -1, And then k The intervals are sorted from small to large at the right end , To satisfy each interval, turn from the back to the front -1 Change to 1.
Then let's talk about why we should sort the intervals from small to large according to the right endpoint , At first, my greedy idea was to give priority to satisfying the large range at the right endpoint , At that time, I felt that 1 Try to fill in the dictionary order later . However, this greed is wrong .

Complete code ：

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 1e5+5;

using namespace std;

struct Query
{
    
	int ai,bi;
	int ci;
}q[maxn];

int n,k,ai,bi,ci;
int a[maxn],mark[maxn];
ll c[maxn];

bool cmp(Query x, Query y) {
     return x.bi<y.bi; }

ll lowbit(ll x) {
     return x&(-x); }

void add(int x, ll val)
{
    
	while(x<=n)
	{
    
		c[x]+=val;
		x+=lowbit(x);
	}
}

ll query(int x)
{
    
	ll ans=0;
	while(x)
	{
    
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}

void solve()
{
    
	memset(mark,0,sizeof(mark));
	memset(c,0,sizeof(c));
	
	for (int i=1; i<=n; i++)
	{
    
		cin>>a[i];
		if (a[i]!=0) {
     mark[i]=1; add(i,a[i]); }
		else {
     a[i]=-1; add(i,a[i]); }  // The first a Set to -1 
	}	
	
	for (int i=1; i<=k; i++) 
		cin>>q[i].ai>>q[i].bi>>q[i].ci;	
		
	sort(q+1,q+k+1,cmp);
	
	for (int i=1; i<=k; i++)
	{
    
		ai=q[i].ai, bi=q[i].bi, ci=q[i].ci;
		int pos=bi;
		while(query(bi)-query(ai-1)<ci && pos>=ai)
		{
    
			if (mark[pos]) {
     pos--; continue; }
			add(pos,2);
			a[pos]=1; mark[pos]=1; pos--;
		}
		if (pos<ai && query(bi)-query(ai-1)<ci )
		{
    
			cout<<"Impossible"<<endl;
			return;
		}
	}
	for (int i=1; i<=n; i++) cout<<a[i]<<' ';
	cout<<endl;
	return;
}

int main()
{
    
   	FAST; 
	while(cin>>n>>k)
	{
    
		solve();
	}
return 0;
}