思考题 specially

Orange Boy And Orange Program

Orange Boy is a programmer of Sunway TaihuLight. One day he wrote the following program to test the super computer:

int n;
int a[100005];
int getAns(int l,int r,int x){
    int ans=0;
    for(int i=l;i<=r;i++){
        if(a[i]<=x){
            ans=max(ans,a[i]);
        }
    }
    return ans;
}
long long query(int l,int r,int x,int k){
    long long sum=0;
    for(int i=0;i<=k;i++){
        sum+=getAns(l,r,x+i);
    }
    return sum;
}

But he is too lazy to test it!
Now you are given n, the array A and q queries.
Each query contains four integers l_i,r_i,x_i,k_i, find the answer of query(l_i,r_i,x_i,k_i)

Constriants

Subtask 1(10%):1\leq n,q,k_i\leq100
Subtask 2(30%):k_i=0
Subtask 3(20%):1\leq n,q,k_i\leq1000
Subtask 4(10%):1\leq A_i\leq 10^5
Subtask 5(30%):l_i=1,r_i=n
For all subtask, 1\leq n,q\leq 10^5,1\leq l_i,r_i\leq n,1\leq A_i,k_i,x_i\leq 10^9

Orange Boy Found It Interesting

Quick Solution By MonkeyKing and XGN

Problem is hard 🙁

First observe.
- Observation 1: the answer of a query is step-like. For example 3 3 3 6 7 7 9
- Observation 2: each element in the answer of a query is either equals to the last element or the position itself(Xi+j).
Then we try to give a formula of the query.
- Assume the different numbers from L to R sorted are M1,M2,M3,M4,M5...,Mt and M1 is the minmax(L,R,Xi)
- Then the answer is M1*k+(M2-M1)*(k-(M2-M1))+(M3-M2)*(k-(M3-M1))+...
Expand the formula:
- formula=M1*k+k(M2-M1)-(M2-M1)^2+k(M3-M2)-(M3-M2)(M3-M1)...=M1*k+kMt-KM1-(M2-M1)^2-(M3-M2)(M3-M1)...=...
- Merge it and found out that some of the items disappeared.
- We left M1*k+M1M2-M1^2..... and stuff
Then observe the formula:
- We can divide the merged formula into three types: M1*Mx,Mx*M(x+1),Mx^2 (1<=x<=t)
- M1*Mx=M1*(M1+M2+M3+...+Mt). So if we know M1 and the sum of all M, answer will be possible.
- Mx*M(x+1). We will talk about this later.
- Mx^2. We will talk about this later.
How to get M1?
- This is quite simple. We can build a segment tree and in each node we store the sorted vector of its sons' elements. Then we do binary search on the segment tree and can get M1 quickly by O(lognlogn)
How to get the sum of all M?
- Still. Build a segment tree and this problem will be solved.
How to get Mx^2?
- Build a segment tree.
How to get Mx*M(x+1)? (By MonkeyKing)
- We do the operations offline.
- For each interval of size sqrt(n) we use a bidirectional-chain to maintain the previous element and the next element
- for every changing from l_i,r_i to l_i+1, r_i+1
- l_i to l_i+1 delete/add at most sqrt(n) elements
- each delete operation costs O(1) time
- and for every sqrt(n) section, r_i moves from 1 to n
- so it's also O(n) for every section
- and moving from l_i, r_i to l_i+1, r_i+1 we can use the previous answer to calc the new one
- say a delete operation is a_i, a_j, a_k
- where a_i < a_j < a_k holds
- and i