链接
题目传送门: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; }
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.
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!
Hi, i feel that i noticed you visited my blog thus i came to go back the choose?.I am
attempting to find issues to enhance my site!I assume
its good enough to make use of a few of your ideas!!
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.
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!
Thanks designed for sharing such a nice thinking, post is good, thats why i have read it fully
Good site you have here.. It’s difficult to find quality writing like yours
these days. I really appreciate individuals like you!
Take care!!
I could not refrain from commenting. Perfectly written!
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.
I know this site provides quality dependent articles or reviews and other information, is
there any other web page which gives these kinds of stuff in quality?
wonderful issues altogether, you just won a emblem new reader.
What would you suggest about your publish that you just made a
few days in the past? Any certain?
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!
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.
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.
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
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 🙂
Touche. Solid arguments. Keep up the good effort.
Quality articles is the secret to be a focus for the people to pay a quick visit the web site, that’s what this website is providing.
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!
It’s hard to find educated people about this subject, however, you seem like you know what
you’re talking about! Thanks
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.
Excellent article. I am experiencing some of these issues as well..
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.
If some one wants expert view about blogging and site-building after that i propose him/her to pay a
quick visit this web site, Keep up the nice job.
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!
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. . . . . .