[문제 풀이] bzoj 4540 HNOI 2016 시퀀스

Description
주어진 길이 n 의 시퀀스: a1, a2,..., an, a [1: n] 로 기록 합 니 다.유사 하 게 a [l: r] (1 ≤ l ≤ r ≤ N) 는 서열: al, al + 1,..., ar - 1, ar 를 가리킨다.만약 1 ≤ l ≤ s ≤ t ≤ r ≤ n 이 라면 a [s: t] 는 a [l: r] 의 하위 서열 이 라 고 부른다.현재 q 개의 질문 이 있 습 니 다. 각 질문 은 두 개의 수 l 과 r, 1 ≤ l ≤ r ≤ n 을 정 하고 a [l: r] 의 서로 다른 하위 서열 의 최소 값 의 합 을 구 합 니 다.예 를 들 어 주어진 서열 은 5, 2, 4, 1, 3 이 고 주어진 두 개의 수 는 1 과 3 이 라 고 묻는다. 그러면 a [1: 3] 는 6 개의 서열 a [1: 1], a [2: 2], a [3: 3], a [2: 3], a [1: 3] 가 있 는데 이 6 개의 서열 의 최소 치 의 합 은 5 + 2 + 4 + 2 + 2 + 2 = 17 이다.
Input
입력 파일 의 첫 줄 은 두 개의 정수 n 과 q 를 포함 하고 각각 시퀀스 길이 와 문의 수 를 대표 합 니 다.다음 줄 은 n 개의 정 수 를 포함 하고 빈 칸 으로 구분 하 며 i 의 정 수 는 ai, 즉 서열 i 의 요소 의 값 입 니 다.다음 q 줄 은 줄 마다 두 개의 정수 l 과 r 를 포함 하고 한 번 의 질문 을 대표 합 니 다.
Output
매번 질문 할 때마다 한 줄 을 출력 하 는 것 은 질문 의 답 을 대표 합 니 다.
Sample Input
5 5 5 2 4 1 3 1 5 1 3 2 4 3 5 2 5
Sample Output
28 17 11 11 17
HINT
1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9
Solution
서열 중의 어떤 숫자 인 Ai 를 고려 하여 왼쪽 의 첫 번 째 작은 숫자 를 기억 하 는 위 치 는 lasti (없 으 면 0) 이 고 오른쪽 에 있 는 첫 번 째 작은 숫자 를 기억 하 는 위 치 는 nexti (없 으 면 n + 1) 입 니 다.우 리 는 이 수가 공헌 한 구간 의 왼쪽 단점 범 위 는 [lasti + 1, i] 이 고 오른쪽 단점 범 위 는 [i, nexti - 1] 임 을 알 수 있다.그래서 우 리 는 한 수의 공헌 범 위 를 평면 위의 사각형 으로 볼 수 있다. 이 평면의 가로 좌 표 는 특정한 구간 의 왼쪽 단점 을 대표 하고 세로 좌 표 는 특정한 구간 의 오른쪽 단점, 즉 평면 상의 점 (L, R) 은 구간 [L, R] 을 대표 한다.그래서 Ai 에 있어 그의 공헌 범 위 는 평면 적 으로 가로 좌표 가 [lasti + 1, i] 이 고 세로 좌 표 는 [i, nexti - 1] 범위 내의 사각형 구역 이다.또한 하나의 질문 [L, R] 에 대해 가로 좌표 가 L 보다 크 고 세로 좌표 가 R 보다 작은 사각형 구역 을 묻 는 것 입 니 다 (우 리 는 기본 평면 에서 R > L 의 지역 공헌 은 0 입 니 다).그래서 문 제 는 우리 에 의 해 평면 사각형 덧셈, 평면 사각형 조회 가중치 와 문제 로 바 뀌 었 다.이것 은 오프라인 + 스캐닝 라인 을 트 리 배열 / 선분 트 리 로 O (nlog2n) 시간 내 에 완성 할 수 있 습 니 다.
평면 사각형 덧셈, 평면 사각형 조회 가중치 와 문제 에 대해 우 리 는 y 에 따라 어 릴 때 부터 대청소 합 니 다.현재 스캐닝 라인 의 높이 는 H 이 고 사각형 의 상 계 는 up 이 며 사각형 의 하 계 는 down 이 며 왼쪽 은 L 이 고 오른쪽 은 R 이 며 현재 사각형 의 가중치 는 val 입 니 다.만약 에 현재 사각형 이 상계 까지 쓸 리 지 않 았 다 면 그 는 가로 좌표 [L, R] 범위 내 에서 모든 점 의 공헌 은 (H - down) * 8727 ° val = H * 8727 ° val - down * 8727 ° val 이다. 우 리 는 두 개의 나무 모양 배열 / 선분 나무 로 각각 가로 좌표 에 있 는 val 과 down * 8727 ° val 을 유지 하고 조회 할 때 하 나 를 곱 하고 하 나 를 더 하 는 것 은 k * 8727 ° H + b 의 형식 이다.즉, 첫 번 째 트 리 배열 에서 모든 가로 세로 표 시 는 현재 H 의 k 값 을 유지 하고 두 번 째 는 b 값 을 유지 합 니 다.현재 사각형 이 상계 로 쓸 어 올 리 고 곧 물 러 날 것 입 니 다. 그러면 그 는 앞으로 가로 좌표 [L, R] 범위 내 에서 모든 점 의 공헌 이 (up - down) * 8727 ° val 입 니 다. 이 공헌 은 더 이상 변 하지 않 기 때문에 우 리 는 이 공헌 을 두 번 째 트 리 / 라인 트 리 에 추가 하여 유지 하고 첫 번 째 라인 트 리 의 val 을 삭제 하면 됩 니 다.
코드:

#include
#include
#include
using namespace std;

template<typename T>inline void read(T &x){
    T f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    x*=f;
}

typedef long long LL;
const int maxn=100010;
int n,m,a[maxn],L[maxn],R[maxn],cnt,sta[maxn],top;
LL ans[maxn];
struct Line{
    int l,r,y,f,id;
    bool operatorconst{
        if(y==b.y)return freturn y2];
struct Bit{
    LL a[maxn],b[maxn];
    Bit(){
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
    }
    void Add(int x,LL val){
        for(int i=x;i<=n;i+=(i&-i))
            a[i]+=val,b[i]+=val*x;
    }
    void Add(int l,int r,LL val){
        Add(l,val);Add(r+1,-val);
    }
    LL Query(int x){
        LL ans=0;
        for(int i=x;i;i-=(i&-i))
            ans+=a[i]*(x+1)-b[i];
        return ans;
    }
    LL Query(int l,int r){
        return Query(r)-Query(l-1);
    }
}k,b;

int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<=n;i++){
        while(top&&a[sta[top]]>=a[i])top--;
        top++;L[sta[top]=i]=sta[top-1];
    }
    sta[top=0]=n+1;
    for(int i=n;i>=1;i--){
        while(top&&a[sta[top]]>a[i])top--;
        top++;R[sta[top]=i]=sta[top-1];
    }
    for(int i=1;i<=m;i++){
        read(q[i].l),read(q[i].y);
        q[i].r=q[i].l;q[i].f=1;q[i].id=i;
    }
    cnt=m;
    for(int i=1;i<=n;i++){
        q[++cnt].l=L[i]+1;q[cnt].f=0;
        q[cnt].r=i;q[cnt].y=i;q[cnt].id=i;
        q[++cnt].l=L[i]+1;q[cnt].f=2;
        q[cnt].r=i;q[cnt].y=R[i]-1;q[cnt].id=i;
    }
    sort(q+1,q+cnt+1);
    for(int i=1;i<=cnt;i++){
        if(!q[i].f){
            k.Add(q[i].l,q[i].r,a[q[i].id]);
            b.Add(q[i].l,q[i].r,(LL)a[q[i].id]*(1-q[i].id));
        }
        else if(q[i].f==2){
            k.Add(q[i].l,q[i].r,-a[q[i].id]);
            b.Add(q[i].l,q[i].r,(LL)a[q[i].id]*q[i].y);
        }
        else ans[q[i].id]=k.Query(q[i].l,n)*q[i].y+b.Query(q[i].l,n);
    }
    for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
    return 0;
}