【BZOJ 4262】Sum

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4262
神犇题解-1:http://www.cnblogs.com/clrs97/p/4824806.html
神犇题解-2:http://blog.csdn.net/qq_34637390/article/details/51313126

题解

我们不妨将所有询问按照右端点\(r_i\) 排序
假设当前处理的所有询问右端点统一为last
定义\(val_i^{last} = \min (\{ {a_j}|j \in [i,last]\} )\)
定义\(sum_i^{last} = \sum\limits_{j = i}^{last} {val_i^j}\)
不难发现对于左右端点在l-r的所有区间的min和为\(\sum\limits_{i = l}^r {sum_i^r}\)
更进一步,每一个原题中提到的询问可以拆成:\(\sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{r_2}}} – \sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{l_2} – 1}}\)

接下来的事情就是用线段树来维护val和sum辣!
考虑last向右移动一个单位,我们首先需要将一些点的val更新
然后我们需要将每一个点当前的val累加到sum里面去

每一个点维护四个变量a,b,c,d来表示标记
定义 new_val = a * val + b * len
定义 new_sum = sum + c * val + d * len
显然更新val需要用到的参数是 {0,val',0,0}
而默认的参数则应该为 {1,0,0,0}
更新sum的参数则应该为 {1,0,1,0}

于是就可以将这两种标记一起下传了
至于为什么可以混在一起?
因为这货是矩阵乘法啊!
ps:矩阵乘法并没有交换律,只有结合律,所以在修改时也得下传标记

Code

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

const int N = 100000+9;
const int M = N << 1;
const int MOD = 1000000000;
const int SEED1 = 1023;
const int SEED2 = 1025;

int n,m,tot,arr[N],stk[N];
LL vout[N];
struct Query{
	int lim,l,r,t,id;
	inline bool operator < (const Query &B) const {
		return lim < B.lim;
	}
}q[M];

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[M][2],L,R,cnt,root;
	LL sum[M],val[M],ans_tmp;
	struct Tag{
		LL a,b,c,d;
		inline Tag() {a=1;b=c=d=0;}
		inline Tag(LL a, LL b, LL c, LL d):a(a),b(b),c(c),d(d) {}
		inline Tag operator * (const Tag &B) {
			return (Tag){a*B.a, B.b+b*B.a, a*B.c+c, B.d+d+b*B.c};
		}
	}tag[M],delta;
	
	void Build(int &w, int l, int r) {
		w = ++cnt;
		tag[w] = Tag(1,0,0,0);
		val[w] = sum[w] = 0;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
		}
	} 
	
	inline void init() {
		cnt = 0;
		Build(root,1,n);
	}
	
	inline void Add(int w, int l, int r, Tag v) {
		static int len; len = r - l + 1;
		sum[w] += val[w] * v.c + len * v.d;
		val[w] = val[w] * v.a + len * v.b;
		tag[w] = tag[w] * v;
	}
	
	inline void push_down(int w, int l, int mid, int r) {
		Add(ch[w][0],l,mid-1,tag[w]);
		Add(ch[w][1],mid,r,tag[w]);
		tag[w] = Tag(1,0,0,0);
	}
	
	inline void GetSum() {
		Add(root,1,n,Tag(1,0,1,0));
	}
	
	void Modify(int w, int l, int r) {
		if (L <= l && r <= R) {
			Add(w,l,r,delta);
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) Modify(ch[w][0], l, mid-1);
			if (R >= mid) Modify(ch[w][1], mid, r);
			val[w] = val[ch[w][0]] + val[ch[w][1]];
			sum[w] = sum[ch[w][0]] + sum[ch[w][1]];
		}
	}
	
	inline void modify(int l, int r, int v) {
		delta = Tag(0,v,0,0);
		L = l, R = r;
		Modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += sum[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) query(ch[w][0], l, mid-1);
			if (R >= mid) query(ch[w][1], mid, r);
		}
	}
	
	inline LL query(int l, int r) {
		ans_tmp = 0;
		L = l; R = r;
		query(root,1,n);
		return ans_tmp;
	}
};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	m = read();
	for (int i=1,l1,l2,r1,r2;i<=m;i++) {
		l1 = read(); r1 = read();
		l2 = read(); r2 = read();
		if (l2 > 1) q[++tot] = (Query){l2-1,l1,r1,-1,i};	
		q[++tot] = (Query){r2,l1,r1,1,i};
		n = max(n, max(r1, r2));
	}
	sort(q+1, q+1+tot);
	for (int i=1,c1=SEED1,c2=SEED2;i<=n;i++) {
		arr[i] = c1 ^ c2;
		c1 = (LL)SEED1 * c1 % MOD;
		c2 = (LL)SEED2 * c2 % MOD;
	}
	
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] > arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] -= SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] < arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] += SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

26 thoughts to “【BZOJ 4262】Sum”

  1. Thanks for another informative blog. Where else may just I am getting that kind of information written in such a
    perfect means? I have a project that I am just now working on, and
    I’ve been at the look out for such information.

  2. Hey there, I think your site might be having browser compatibility issues.
    When I look at your website in Safari, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up!
    Other then that, wonderful blog!

  3. Heya i’m for the first time here. I came across
    this board and I find It really useful & it helped me out much.
    I hope to give something back and aid others like you helped
    me.

  4. Hi! This post couldn’t be written any better! Reading
    through this post reminds me of my good old room mate!
    He always kept talking about this. I will forward this page
    to him. Pretty sure he will have a good read. Many thanks for
    sharing!

  5. I got this site from my buddy who informed me on the topic of
    this web page and at the moment this time I am visiting this web site
    and reading very informative posts at this time.

  6. Wow, amazing weblog format! How lengthy have you been blogging for?

    you made running a blog look easy. The full glance of your site
    is excellent, as well as the content material!

  7. Does your website have a contact page? I’m having problems locating it but, I’d like to shoot you an e-mail.
    I’ve got some creative ideas for your blog you might be interested in hearing.
    Either way, great website and I look forward to
    seeing it develop over time.

  8. Hi there! Someone in my Facebook group shared this site with us so I came to take a look.
    I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
    Wonderful blog and wonderful design and style.

  9. I believe that is one of the so much vital info for me. And i am satisfied reading your article.
    However want to statement on few general issues, The website
    taste is great, the articles is really great : D.
    Excellent process, cheers

  10. I haven’t checked in here for some time since I thought it was getting boring, but the last several posts are good quality so I guess I will add you back to my daily bloglist. You deserve it my friend 🙂

  11. Hello there, just became aware of your blog through Google,
    and found that it’s really informative. I’m gonna watch out for brussels.
    I will be grateful if you continue this in future. Numerous people
    will be benefited from your writing. Cheers!

  12. I do accept as true with all the ideas you have presented to your
    post. They’re very convincing and can certainly work.
    Still, the posts are very quick for starters. May just you
    please prolong them a little from subsequent time? Thank you for the
    post.

  13. I’m gone to say to my little brother, that he should also pay a quick visit this web site on regular basis to take
    updated from newest information.

  14. great put up, very informative. I ponder why the other specialists
    of this sector do not realize this. You should
    continue your writing. I am sure, you have a great readers’ base already!

  15. Whats up very nice blog!! Guy .. Excellent .. Amazing .. I will bookmark your blog and take the feeds additionallyKI’m glad to search out so many helpful info here in the put up, we need develop extra strategies in this regard, thank you for sharing. . . . . .

Leave a Reply

Your email address will not be published. Required fields are marked *