2025.5.16
/*#include <stdio.h>
int main()
{
int n, q, i, j, a, l, r, t, temp;
int x[200000]={}, cnt[1000]={}, result[200000]={};
scanf("%d%d", &n, &q);
for(i=0; i<n; i++){
scanf("%d", &x[i]);
}
for(i=0; i<q; i++){
scanf("%d%d", &l, &r);
a=0;
for(j=0; j<n; j++){
if(x[j]>=l&&x[j]<=r){
for(t=0; t<n; t++){
if(x[t]>=l&&x[t]<=r){
if(j>=t){
cnt[a]+=(x[j]-x[t]);
}
else{
cnt[a]+=(x[t]-x[j]);
}
}
}
a++;
}
if(x[j]>r){
break;
}
}
for(j=0; j<a; j++){
int max=j;
for(t=j+1; t<=n; t++){
if(cnt[t]>cnt[max]){
max=t;
}
}
temp = cnt[j];
cnt[j] = cnt[max];
cnt[max] = temp;
}
a=0;
j=0;
while(cnt[j+1]!=0){
a+=cnt[j]-cnt[j+1];
cnt[j]=0;
j++;
}
cnt[j]=0;
result[i]=a;
}
for(i=0; i<q; i++){
printf("%d\n", result[i]);
}
return 0;
}
*/
#include<stdio.h>
int x[200000]={};
int bs(int s, int e, int l, int r)//l~r 사이에 있는 가장 작은 수를 찾아낸다
{
while(s<=e){
int mid=(s+e)/2;
if(x[mid]<l){
return bs(mid+1, e, l, r);
}
else if(x[mid]>r){
return bs(s, mid-1, l, r);
}
else if(x[mid-1]>=l&&x[mid-1]>=r){
return bs(mid+1, e, l, r);
}
return mid;
}
return -1;
}
int compare(const int* a, const int* b)
{
if(*a<*b){
return -1;
}
else if(*a>*b){
return 1;
}
else{
return 0;
}
}
int main()
{
int n, q, i, j=0, t, l, r, a;
int cnt[200000]={};
scanf("%d%d", &n, &q);
for(i=0; i<n; i++){
scanf("%d", &x[i]);
}
for(i=0; i<q; i++){
scanf("%d%d", &l, &r);
a=0;
j=bs(0, n-1, l-1, r-1);
printf("test%d\n", j);
t=j;
while(x[j]<=r){
while(x[t]<=r){
if(j>=t){
cnt[a]+=(x[j]-x[t]);
}
else{
cnt[a]+=(x[t]=x[j]);
}
}
a++;
}
a=0;
j=0;
qsort(cnt, q, sizeof(int), compare);
while(cnt[j+1]!=0){
a+=cnt[j+1]-cnt[j];
cnt[j]=0;
j++;
}
cnt[j]=0;
printf("%d\n", cnt);
}
return 0;
}