思考题 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 , find the answer of

Constriants

Subtask 1(10%):
Subtask 2(30%):
Subtask 3(20%):
Subtask 4(10%):
Subtask 5(30%):
For all subtask,

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<j<k holds too
- to delete a_j, a_i_right=... ... ..., and res should += a_i*a_k -a_i*a_j-a_i*a_k
- add operation is similar
- when you move from l_i, r_i to l_i+1, r_i+1
- note that l_i, r_i is the index of the unsorted array
- take move from l_i to l_i+1 for exmaple
- find all position in the sorted array whose index in its unsorted array is l_i, (l_i)+1, (l_i)+2 ... , (l_(i+1))
- then perform the del operation
- This part runs totally in O(sqrt(n)) for ONE query

Then let's mix them up together.

- We do the queries offline, sort it in increasingly L.

- Build many segments tree maintaining things above.

- Use bidirectional-chain to maintain the value to get Mx*M(x+1)

- Then use the formula to get the answer for each of the query.

That's all. Total Solution runs in O(q(lognlogn+sqrt(n)) which should be passing (when TL=10s).