蒟蒻的数列 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新技能：分治线段树。