链接
题目传送门: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;
}