首页 > 其他分享 >「杂题乱刷2」CF1108E2

「杂题乱刷2」CF1108E2

时间:2024-09-17 22:13:43浏览次数:10  
标签:CF1108E2 forl 复杂度 区间 return 杂题 define

题目链接

CF1108E1(luogu)

CF1108E2(luogu)

CF1108E1(codeforces)

CF1108E2(codeforces)

解题思路

这篇题解分 E1,E2 两个部分来讲。

E1 sol:

我们发现可以暴力枚举最后经过所有操作之后的最大值,那么显然的,我们将不会做任何经过这个位置的操作,会做不经过这个区间的所有操作。

直接暴力进行操作即可。

时间复杂度 \(O(n^2 + nm)\)。

B2 sol:

发现这个暴力的过程可以使用区间加,区间最大值,区间最小值的线段树来维护,此时时间复杂度变为 \(O(nm \log n)\),并不能通过此题,那么此时,我们可以再打一个标记表示当前树内是否加过这个区间,由于区间是连续的一段,并且我们枚举的最大值也是连续的一段,因此有一个性质,那就是每个区间至多被操作过两次,此时时间复杂度变为 \(O(n + m \log n)\),可以通过此题。

参考代码

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll int
#define pb push_back
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define mid ((l+r)>>1)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}
template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}
ll _t_;
void _clear(){}
/*
0 -4 1 1 2
*/
ll n,m;
ll id;
ll maxn;
ll a[100010],b[100010],c[100010];
ll l[100010],r[100010];
ll vis[510];
struct node{
    ll l,r,minn,maxn,tag;
}tree[400010];
struct nide{
	ll x,id;
}d[100010];
bool cmp(nide x,nide y){
	return x.x<y.x;
}
void pushup(ll x){
    tree[x].minn=min(tree[x*2].minn,tree[x*2+1].minn);
    tree[x].maxn=max(tree[x*2].maxn,tree[x*2+1].maxn);
}
void pushdown(ll x)
{
    tree[x*2].minn+=tree[x].tag;
    tree[x*2+1].minn+=tree[x].tag;
    tree[x*2].tag+=tree[x].tag;
    tree[x*2+1].tag+=tree[x].tag;
    tree[x*2].maxn+=tree[x].tag;
    tree[x*2+1].maxn+=tree[x].tag;
    tree[x].tag=0;
}
void build(ll x,ll l,ll r)
{
    tree[x].l=l,tree[x].r=r;
    if(l==r)
    {
        tree[x].minn=a[l];
        tree[x].maxn=a[l];
        return ;
    }
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
}
void add(ll x,ll l,ll r,ll y)
{
    if(l<=tree[x].l && tree[x].r<=r)
    {
        tree[x].minn+=y;
        tree[x].maxn+=y;
        tree[x].tag+=y;
        return ;
    }
    pushdown(x);
    ll Mid=(tree[x].l+tree[x].r)/2;
    if(l<=Mid)
        add(x*2,l,r,y);
    if(Mid<r)
        add(x*2+1,l,r,y);
    pushup(x);
}
ll querymin(ll x,ll l,ll r)
{
    if(l<=tree[x].l && tree[x].r<=r)
        return tree[x].minn;
    pushdown(x);
    ll Mid=(tree[x].l+tree[x].r)/2,ans=1e9;
    if(l<=Mid)
        Min(ans,querymin(x*2,l,r));
    if(Mid<r)
        Min(ans,querymin(x*2+1,l,r));
    return ans;
}
ll querymax(ll x,ll l,ll r)
{
    if(l<=tree[x].l && tree[x].r<=r)
        return tree[x].maxn;
    pushdown(x);
    ll Mid=(tree[x].l+tree[x].r)/2,ans=-1e9;
    if(l<=Mid)
        Max(ans,querymax(x*2,l,r));
    if(Mid<r)
        Max(ans,querymax(x*2+1,l,r));
    return ans;
}
ll check(ll x)//x最终为最大值 
{
//	forl(i,0,n+2)
//		c[i]=0;
	forl(i,1,m)
	{
		if(l[i]>x || r[i]<x)
		{
			if(!vis[i])
				add(1,l[i],r[i],-1),vis[i]=1;
		}
		else
		{
			if(vis[i])
				add(1,l[i],r[i],1),vis[i]=0;
		}
	}
			//c[l[i]]--,c[r[i]+1]++;
//	forl(i,1,n)
//		c[i]+=c[i-1];
	ll maxn=-1e9,minn=1e9;
	maxn=querymax(1,1,n),minn=querymin(1,1,n);
//	forl(i,1,n)
//		cout<<querymax(1,i,i)<<' ';
//	cout<<endl;
//	forl(i,1,m)
//		if(l[i]>x || r[i]<x)
//			add(1,l[i],r[i],1);
///	forl(i,1,n)
//		Max(maxn,c[i]+a[i]),
//		Min(minn,c[i]+a[i]);
//		cout<<a[i]+c[i]<<' ';
//	cout<<endl;
//	cout<<"<"<<minn<<' '<<maxn<<endl;
	return maxn-minn;
}
void check2(ll x)//x最终为最大值 
{
	vector<ll>ans;
	forl(i,0,n+2)
		c[i]=0;
	forl(i,1,m)
		if(l[i]>x || r[i]<x)
			ans.pb(i);
	cout<<ans.size()<<endl;
	for(auto i:ans)
		cout<<i<<' ';
//		{
//			cout<<
//		}
//			c[l[i]]--,c[r[i]+1]++;
//	forl(i,1,n)
//		c[i]+=c[i-1];
//	ll maxn=-1e18,minn=1e18;
///	forl(i,1,n)
//		Max(maxn,c[i]+a[i]),
//		Min(minn,c[i]+a[i]);
//		cout<<a[i]+c[i]<<' ';
//	cout<<endl;
//	cout<<minn<<' '<<maxn<<endl;
//	return maxn-minn;
}
void solve()
{
	_clear();
	cin>>n>>m;
	forl(i,1,n)
		cin>>a[i];//,d[i].x=a[i],d[i].id=i;
	build(1,1,n);
	forl(i,1,m)
		cin>>l[i]>>r[i];
	maxn=-1e9;
//	check(5);
//	sort(d+1,d+1+n,cmp);
	forl(i,1,n)
		if(Max(maxn,check(i)))
			id=i;
/*	forr(i,n,max(5001,n-5000))
		if(Max(maxn,check(i)))
			id=i;	*/
	cout<<maxn<<endl;
	check2(id);
	
}
int main()
{
//	freopen("tst.txt","r",stdin);
//	freopen("sans.txt","w",stdout);
	IOS;
	_t_=1;
 //	cin>>_t_;
	while(_t_--)
		solve();
	QwQ;
}

标签:CF1108E2,forl,复杂度,区间,return,杂题,define
From: https://www.cnblogs.com/wangmarui/p/18417630

相关文章

  • 「杂题乱刷2」CF1527B2
    题目链接CF1527B1(luogu)CF1527B2(luogu)CF1527B1(codeforces)CF1527B2(codeforces)解题思路这篇题解分B1,B2两个部分来讲。B1sol:考虑字符串中\(0\)的数量,设这个值为\(sum\):若\(sum\equiv0\pmod{2}\),且字符串回文时,那么此时,后手可以一直模仿先手的操作,直到字符串含有......
  • 杂题乱做 - 2000-
    目录写在前面CF1992F贪心,数学1900CF2008G贪心,数学1800CF2009G1数据结构1900CF1891D数学1900CF1996F二分,简单数学1900CF1985G数学1600写在最后写在前面简单题们。以后可以用来搬。唉唉现在2000及以下都能直接秒了真没意思。CF1992F贪心,数学1900显然直接贪心......
  • 9月杂题
    [ABC310F]Make10Again分母是\(\proda_i\),只需求分子。首先要发现投出了\(10\)以上的点数是无用的,所以只需考虑\(10\)以内的。思考如何计数,发现转移依赖于前面的点数和的方案数,而且\(10\)很小,考虑状压DP,设\(f_{i,s}\)表示前\(i\)个骰子,状态为\(s\)的方案数,转......
  • 杂题乱做
    BalticOI2021A.ADifficultyChoice蓝题做不出来?蓝题做不出来?蓝题做不出来?发现要求是这\(k\)个数和在\([A,2A]\)之间,这个\(2A\)肯定有说法。分类讨论有没有选择\(\geqA\)的数。如果选择了,一定是仅选择一个\(\geqA\)中最小的数,这时已经满足\(\geqA\)了,剩下的肯......
  • 「杂题乱刷2」CF1301C
    怎么没有二分的题解啊,写一篇。题目链接CF1301CAyoub'sfunction解题思路发现我们可以将问题转化成将\(n-m\)个\(1\)分成\(m\)份,设第\(i\)份的数字之和为\(sum_i\),则这样的分配方案的贡献为\(\frac{n\times(n+1)}{2}-\sum_{i=1}^{n}sum_i^2\)。容易发现要使......
  • 杂题总结
    杂题总结记号约定不难注意意味着我在初见的时候想到了难以注意意味着我没有注意到P8421[THUPC2022决赛]rsraogpsP8421[THUPC2022决赛]rsraogps-洛谷|计算机科学教育新生态(luogu.com.cn)首先套路性扫描线,然后这个问题就变成增量构造。不难注意不知怎么......
  • 「杂题乱刷2」CF862D
    简单题。题目链接CF862DMahmoudandEhabandthebinarystring解题思路首先我们可以发现,字符串的第一个字母不是\(1\)就是\(0\),因此我们可以容易花费\(2\)次询问来找到数字\(0\)或数字\(1\)所在的一个位置。然后,显然的,我们以先找到的数字为\(0\)为例,那么我们就......
  • 「杂题乱刷2」CF862C
    怎么题解区里都没有随机化的题解啊/jy。于是就有了这篇题解。题目链接CF862CMahmoudandEhabandthexor解题思路思路非常简单。首先容易发现在\(n=1\)时,直接构造一个\(x\)这个数即可。其次我们考虑\(n=2\)的情况,由于异或的基本性质,我们可以得出当\(x=0\)......
  • 「杂题乱刷2」CF1493C
    题目链接K-beautifulStringsCF1493C解题思路首先,如果原字符串是合法的直接输出原字符串即可。然后我们考虑一个最简单的暴力,你枚举第一个你构造的字符串比原串大的字符的位置,再枚举这个字符,然后后面的肯定是从后往前贪心放即可,在此不再赘述。这样的复杂度是\(O(|S|^2\tim......
  • 「杂题乱刷2」CF1567D
    duel到的。题目链接CF1567D解题思路发现在越高的数位上,你获取的利益就会越大。因此你肯定是每次将尽可能多的数分到最高的数位上是最优的。但是你会发现,有可能你这样分数位后后面的数就分不到权值了,你只需要保证去掉当前分掉的权值之后,剩下可以分的权值不小于还剩下没分到......