Array Transformer UVA

题意：

给你n个数，要进行m次操作

对于每次操作(l,r,v,p)代表：在区间[l,r]中有x(这个x是需要你自己找出来的)个数小于v，你需要把序列的第p个位置的值改成u∗k/(r−l + 1)

最后输出序列就完了

题解：

因为他要找出来区间中有多少数小于v，所以我们就要维护一个数组a，在这个a数组里面要放置每一块排序后的结束(我的代码是从小到大排序)。为什么要排序，因为对于一个序列排完序之后我们可以通过二分找出来小于v的那个数的位置，然后我们又知道每一个块的左区间位置和右区间位置，所以可以很简单求出来x的值

具体操作见代码：

  1 #include <iostream>

  2 #include<stdio.h>

  3 #include<string.h>

  4 #include<algorithm>

  5 #include<math.h>

  6 using namespace std;

  7 const int maxn=300005;

  8 int a[maxn],L[maxn],R[maxn],belong[maxn],b[maxn];

  9 int l,r,v,p,n,m,u;

 10 void build()

 11 {

 12     int len=sqrt(n);

 13     int ci=n/len;

 14     for(int i=1; i<=ci; ++i)

 15     {

 16         L[i]=len*(i-1)+1;

 17         R[i]=len*i;

 18     }

 19     R[ci]=n;

 20

 21     for(int i=1; i<=ci; ++i)

 22     {

 23         for(int j=L[i]; j<=R[i]; ++j)

 24         {

 25             belong[j]=i;

 26         }

 27         sort(a+L[i],a+R[i]+1);

 28     }

 29 }

 30 int query()

 31 {

 32     int ans=0;

 33     if(belong[l]==belong[r])

 34     {

 35         for(int i=l; i<=r; ++i)

 36         {

 37             if(b[i]<v) ans++;

 38         }

 39     }

 40     else

 41     {

 42         for(int i=l; i<=R[belong[l]]; i++) ans+=b[i]<v;

 43         for(int i=belong[l]+1; i<belong[r]; i++)

 44             ans+=lower_bound(a+L[i],a+R[i]+1,v)-a-L[i];

 45         for(int i=L[belong[r]]; i<=r; i++) ans+=b[i]<v;

 46     }

 47     return ans;

 48 }

 49 void update(int x)

 50 {

 51     int pos=lower_bound(a+L[belong[p]],a+R[belong[p]]+1,b[p])-a;

 52     x=(long long)u*x/(r-l+1);

 53     a[pos]=x;

 54     if(b[p]>x)

 55     {

 56

 57         for(int i=pos; i>L[belong[p]]; i--)

 58         {

 59             if(a[i]<a[i-1]) swap(a[i],a[i-1]);

 60             else break;

 61         }

 62     }

 63     else if(b[p]<x)

 64     {

 65

 66         for(int i=pos; i<R[belong[p]]; i++)

 67         {

 68             if(a[i]>a[i+1]) swap(a[i],a[i+1]);

 69             else break;

 70         }

 71     }

 72     b[p]=x;

 73 }

 74 int main()

 75 {

 76

 77     while(~scanf("%d%d%d",&n,&m,&u))

 78     {

 79         for(int i=1; i<=n; ++i)

 80             scanf("%d",&a[i]),b[i]=a[i];

 81         build();

 82         while(m--)

 83         {

 84             scanf("%d%d%d%d",&l,&r,&v,&p);

 85             update(query());

 86         }

 87         for(int i=1; i<=n; ++i)

 88         {

 89             printf("%d\n",b[i]);

 90         }

 91     }

 92     return 0;

 93 }

 94 /*

 95 10 1 11

 96 1

 97 2

 98 3

 99 4

100 5

101 6

102 7

103 8

104 9

105 10

106 2 8 6 10

107 */

巴特西

Array Transformer UVA - 12003

最新文章

热门文章