BZOJ4540: [Hnoi2016] 시퀀스(세그먼트 트리)

전송문
문제풀이: 이 문제의 라인 트리는 정말 신기하다.
1 1에서 n n으로 직접 스캔하여 1 ~ i 1 ~ i에서 i i의 최소값을 계속 업데이트하는 것을 고려합니다.
그러면 분명히 우리는 세그먼트 트리에 대해 세그먼트 덮어쓰기를 지원하고, 세그먼트 트리에 대해 역사와 역사를 구해야 한다.
그리고 우리는 각 노드의 구조에 대해 행렬을 구성하여 완성할 수 있다
⎛⎝⎜⎜svallen⎞⎠⎟⎟ ( s v a l l e n )
구간 덮어쓰기를 완성할 수 있습니다.(주로 하나 더 유지 관리
len l e n )
조회는 직접 화해를 구하면 된다.

#include 
typedef long long LL;
using namespace std;
inline int rd() {
    char ch=getchar(); int i=0,f=1;
    while(!isdigit(ch)) {if(ch=='-')f=-1; ch=getchar();}
    while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=getchar();}
    return i*f;
}
const int N=1e5+50;
int n,q,a[N],p[N],st[N],top;
vector < pair<int,int> >qry[N];
struct Tag {
    LL a,b,c,d;
    Tag(LL a=0,LL b=0,LL c=1,LL d=0):a(a),b(b),c(c),d(d){}
    friend inline Tag operator *(const Tag &a,const Tag &b) {
        return Tag(b.a+a.a*b.c, b.b+a.a*b.d+a.b, a.c*b.c, a.c*b.d+a.d);
    } 
}tag[N*4];
LL s1[N*4],s2[N*4],ans[N];
inline void modify(int k,int l,int r,Tag t) {
    s1[k]=s1[k]+t.a*s2[k]+t.b*(r-l+1);
    s2[k]=t.c*s2[k]+t.d*(r-l+1);
    tag[k]=t*tag[k];
}
inline void pushdown(int k,int l,int r) {
    int mid=(l+r)>>1;
    modify(k<<1,l,mid,tag[k]);
    modify(k<<1|1,mid+1,r,tag[k]);
    tag[k]=Tag(0,0,1,0);
}
inline void upt(int k) {
    s1[k]=s1[k<<1]+s1[k<<1|1];
    s2[k]=s2[k<<1]+s2[k<<1|1];
}
inline void modify(int k,int l,int r,int L,int R,Tag t) {
    if(L<=l&&r<=R) {modify(k,l,r,t); return;}
    pushdown(k,l,r);
    int mid=(l+r)>>1;
    if(R<=mid) modify(k<<1,l,mid,L,R,t);
    else if(L>mid) modify(k<<1|1,mid+1,r,L,R,t);
    else modify(k<<1,l,mid,L,R,t),modify(k<<1|1,mid+1,r,L,R,t);
    upt(k);
}
inline LL query(int k,int l,int r,int L,int R) {
    if(L<=l&&r<=R) {return s1[k];}
    pushdown(k,l,r);
    int mid=(l+r)>>1;
    if(R<=mid) return query(k<<1,l,mid,L,R);
    else if(L>mid) return query(k<<1|1,mid+1,r,L,R);
    else return query(k<<1,l,mid,L,R)+query(k<<1|1,mid+1,r,L,R);
}
int main() {
    n=rd(), q=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=q;i++) {
        int x=rd(), y=rd();
        qry[y].push_back(make_pair(x,i));
    }
    for(int i=1;i<=n;i++) {
        while(top&&st[top]>=a[i]) --top;
        modify(1,1,n,p[top]+1,i,Tag(0,0,0,a[i]));
        st[++top]=a[i]; p[top]=i;
        modify(1,1,n,1,i,Tag(1,0,1,0));
        for(int j=qry[i].size()-1;~j;j--) {
            int v=qry[i][j].first;
            ans[qry[i][j].second]=query(1,1,n,v,i);
        }
    }
    for(int i=1;i<=q;i++) printf("%lld
",ans[i]);
}