【ZJ c259】 kevin 改區間

第一篇文章ww
原題連結：https://zerojudge.tw/ShowProblem?problemid=c259
剛看到的時候覺得是經典題，但沒什麼想法
拜某建中的蔣大大傳了篇文章之後才搞懂這精湛的解法
寫完之後居然一次過了Orz 人品爆發(?

解題概念：
開一棵線段樹，維護以下：
1.總和(sum)
2.最小值(Min)
3.最小值的個數(min_count)
4.次小值(sec_min)，葉節點預設INF
5.懶標(lazy)

前4個在未修改的情況下的維護是很簡單的
關鍵在「修改值」
對於一個線段樹上的node和V取MAX，分成3個case來處理：
case 1:V<=min
　　return
case 2:V<sec_min
　　利用min_count和Min做運算後維護sum，把Min和lazy覆蓋掉後return
case 3:V>=sec_min
　　暴力往下推左右兒子

如果不觸發case 3的話，複雜度會是完美的O(QlogN)
而對於case 3的複雜度分析，考慮每次遞迴後，因為是對整個node取MAX，則數字種數必定會減少1，至多減少node的區間大小次，所以減少的次數是呈線性的，複雜度為O(NlogN)

總複雜度約為O((N+Q)logN)

	#pragma GCC optimize ("Ofast")
	#include <iostream>
	#include <algorithm>
	#include <vector>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define pb push_back
	#define ll long long
	using namespace std;
	struct node
	{
	ll sum,Min,sec_min,min_count=1,lazy=0;
	node *l=nullptr,*r=nullptr;
	void up()
	{
	sum=0;
	if(l)
	{
	sum=l->sum+r->sum;
	if(l->Min<r->Min)
	Min=l->Min,min_count=l->min_count,sec_min=min(l->sec_min,r->Min);
	else if(l->Min>r->Min)
	Min=r->Min,min_count=r->min_count,sec_min=min(r->sec_min,l->Min);
	else
	Min=l->Min,min_count=l->min_count+r->min_count,sec_min=min(l->sec_min,r->sec_min);
	}
	}
	void down()
	{
	if(!lazy) return;
	if(l)
	{
	if(l->Min>=lazy) ;
	else if(l->sec_min>lazy) l->sum+=(lazy-l->Min)*l->min_count,l->Min=l->lazy=lazy;
	else l->lazy=lazy,l->down(),l->up();
	if(r->Min>=lazy) ;
	else if(r->sec_min>lazy) r->sum+=(lazy-r->Min)*r->min_count,r->Min=r->lazy=lazy;
	else r->lazy=lazy,r->down(),r->up();
	}
	lazy=0;
	}
	}*head=nullptr;
	node *build(ll l,ll r)
	{
	node *p=new node;
	if(l==r) return cin >> p->sum,p->Min=p->sum,p->sec_min=1000000000001,p;
	ll m=(l+r)/2;
	return p->l=build(l,m),p->r=build(m+1,r),p->up(),p;
	}
	ll query(ll L,ll R,ll l,ll r,node *p)
	{
	p->down();
	if(L<=l && R>=r) return p->sum;
	ll m=(l+r)/2,re=0;
	if(L<=m) re=query(L,R,l,m,p->l);
	if(R>m) re+=query(L,R,m+1,r,p->r);
	return re;
	}
	void modify(ll L,ll R,ll l,ll r,node *p,ll v)
	{
	p->down();
	if(L<=l && R>=r)
	{
	if(p->Min>=v) ;
	else if(p->sec_min>v) p->sum+=(v-p->Min)*p->min_count,p->Min=p->lazy=v;
	else p->lazy=v,p->down(),p->up();
	return;
	}
	ll m=(l+r)/2;
	if(L<=m) modify(L,R,l,m,p->l,v);
	if(R>m) modify(L,R,m+1,r,p->r,v);
	p->up();
	}
	int main()
	{jizz
	ll n,m,l,r,v,k;
	cin >> n >> m;
	head=build(1,n);
	while(m--)
	{
	cin >> k >> l >> r;
	if(k==1)
	cin >> v,modify(l,r,1,n,head,v);
	else
	cout << query(l,r,1,n,head) << "\n";
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub