[bzoj4636]蒟蒻的数列

蒟蒻的数列 bzoj-4636

题目大意：给定一个序列，初始均为0。n次操作：每次讲一段区间中小于k的数都变成k。操作的最后询问全局和。

注释：$1\le n\le 4\cdot 10^4$。

想法：那个操作就是一个不好好说话的操作，说白了就是对区间的每一个数取max

然后我们对于那个序列建立分治线段树。每个操作我都把它挂在对应的log的点上。

n个操作都执行完了之后我们从1号节点深搜，更新答案即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define inf 1e9

#define N 40010

using namespace std;

typedef long long ll;

ll maxn[N*40],ans=0;

int ls[N*40],rs[N*40],cnt;

int root;

inline char nc()

{

	static char *p1,*p2,buf[100000];

	return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

ll read()

{

	ll x=0; char c=nc();

	while(!isdigit(c)) c=nc();

	while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=nc();

	return x;

}

void update(int x,int y,ll val,int l,int r,int &pos)

{

	if(!pos) pos=++cnt;

	if(x==l&&r==y)

	{

		maxn[pos]=max(maxn[pos],val);

		return;

	}

	int mid=(l+r)>>1;

	if(y<=mid) update(x,y,val,l,mid,ls[pos]);

	else if(mid<x) update(x,y,val,mid+1,r,rs[pos]);

	else

	{

		update(x,mid,val,l,mid,ls[pos]);

		update(mid+1,y,val,mid+1,r,rs[pos]);

	}

	// if(x<=mid) update(x,y,val,l,mid,ls[pos]);

	// if(mid<y) update(x,y,val,mid+1,r,rs[pos]);

}

void query(ll val,int l,int r,int pos)

{

	if(!pos) return;

	maxn[pos]=max(maxn[pos],val);

	if(!ls[pos]&&!rs[pos])

	{

		ans+=maxn[pos]*(r-l+1);

		return;

	}

	int mid=(l+r)>>1;

	query(maxn[pos],l,mid,ls[pos]);

	query(maxn[pos],mid+1,r,rs[pos]);

	if(!ls[pos]) ans+=maxn[pos]*(mid-l+1);

	if(!rs[pos]) ans+=maxn[pos]*(r-mid);

}

int main()

{

	int n=read();

	int x,y; ll val;

	for(int i=1;i<=n;++i)

	{

		x=read(),y=read(),val=read();

		if(x==y) continue;

		update(x,y-1,val,1,inf,root);

	}

	query(0,1,inf,root);

	printf("%lld\n",ans);

	return 0;

}

小结：get新技能：分治线段树。

巴特西

[bzoj4636]蒟蒻的数列_线段树

最新文章

热门文章