战斗与区间

讲个笑话，我光搓这$35$组数据就花了$1h$(以前没干过一直出小错误)，全随机数据如果太水了别喷

这个题本人的做法可能并非期望正解且码量较大(差点被$luogu$卡常$GG$)，但是好想，这里分享出来

第一眼看到这个题的时候：欸！区间问题，那我直接开始$SegmentTree$你不炸了吗

事实证明我的想法是正确的，对于此题，我们只需要记录下每个区间的最大值，如果比$k$小就可以直接跑路

这也是线段树题目中较常用的思想：单点暴力，区间优化

这样我们就能过这道题目了(考场忘初始化爆零力QAQ)

#include <bits/stdc++.h>
using namespace std;

const int N=3e5+10;

struct node
{
	int l, r, k, idx;
	bool operator <( const node &x )const
	{
		return k > x.k;
	}
}query[N];

struct Segment_Tree
{
	int l, r, maxn, sum;
}st[N<<2];

int a[N];

void build( int p,int l,int r )
{
	st[p].l=l, st[p].r=r; 
	if( l == r )
	{
		st[p].sum=0, st[p].maxn=a[l];
		return ;
	}
	int mid=( l+r )>>1;
	build( p<<1,l,mid );
	build( p<<1|1,mid+1,r );
	st[p].maxn=max( st[p<<1].maxn,st[p<<1|1].maxn );
}

int ask( int p,int l,int r,int k )
{
	if( st[p].l >= l && st[p].r <= r && st[p].maxn <= k )
	{
		return st[p].sum;
	} 
	if( st[p].l == st[p].r )
	{
		while( st[p].maxn > k )
		{
			st[p].maxn>>=1;
			st[p].sum++;
		}
		return st[p].sum;
	}
	int mid=( st[p].l+st[p].r )>>1;
	int ans=0;
	if( mid >= l )  ans+=ask( p<<1,l,r,k );
	if( mid < r )	ans+=ask( p<<1|1,l,r,k );
	st[p].maxn=max( st[p<<1].maxn,st[p<<1|1].maxn );
	st[p].sum=st[p<<1].sum+st[p<<1|1].sum;
	return ans;
}

int main(){
	// freopen( "C:\\Users\\A\\Desktop\\all\\code\\down\\big20.in","r",stdin );
	// freopen( "C:\\Users\\A\\Desktop\\all\\code\\down\\big20.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr );
	cout.tie( nullptr );
	int n, q;
	cin>>n>>q;
	for( int i=1;i<=n;i++ )
	{
		cin>>a[i];
	}
	for( int i=1;i<=q;i++ )
	{
		cin>>query[i].l>>query[i].r>>query[i].k;
		query[i].idx=i;
	}
	sort( query+1,query+q+1 );
	vector< int > ans( q+1 );	
	build( 1,1,n );
	for( int i=1;i<=q;i++ )
	{
		ans[query[i].idx]=ask( 1,query[i].l,query[i].r,query[i].k );		
	}
	for( int i=1;i<=q;i++ )
	{
		cout<<ans[i]<<"\n";
	}
	return 0;
}