This contest is a little hard for me. Only A and C were solved finally though I spent more than one hour on the other problems. My rank is 213. Here is the summary:
Pro A: There are n elements in an array.If we can obtain an array where any two neighboring elements would be distinct in a finite time,print "YES" and print "NO" otherwise.
This problem is not hard.What we should do is just counting the amount of each elements and find the max amount k.If k-1 is bigger than n-k,then print "NO" and print "YES" otherwise.
Pro C: The first line tells us three integers n, m, k(1<=n,m,k<=10^5). The second line is an array(f) of n elements.
Next m lines contain operations with three integers li, ri, di(1<=li<=ri<=n,0<=di<=10^5) which means to increase all array elements with numbers li,li+1,...,ri by value di.
Next k lines contain queries with two integers x, y(1<=xi<=yi<=m) which means that one should apply operations with numbers xi,xi+1,..., yi to the array.
After understanding this problem,I thought of the segment tree firstly with the max data 10^5.But after I analysed carefully,I find another convenient solution.
First of all, we need to know how many times each operations need to apply by k queries.We need an array(p) with each element is 0 initially.Then come k queries and execute two commands:p[xi]++ and p[yi+1]--.After cycling from 1 to m with executing command:p[i]+=p[i-1],we can know the i-th operation needs to apply p[i] times.
Secondly,we multiply each operation's di by p[i].
Thirdly,we need to know how much each element needs to add by m operations.The following is similar to the first.As mentioned,we need an array(p) with each element is 0 initially.Then come m operations and execute two commands:p[li]+=di and p[ri+1]-=di.After cycling from 1 to n with executing command:p[i]+=p[i-1],we can know each element f[i] needs to add p[i].
Finally,after cycling from 1 to n with executing command:f[i]+=p[i],we can obtain the answers.
*Tips:as the data will be very big,we should use __int64 replace of int.
