hdu5737

首先思考一个朴素的做法

将b[]维护成一个线段树套有序表,每次修改a[]用线段树+lazy tag

并在线段树的子区间上在有序表中二分更新这段区间中a[i]>=b[i]的值,复杂度O(nlog^2)

有没有更优的做法?

考虑在一次修改操作中,查询的数是相同的,并且b[]这个有序表始终不变

因此在生成b[]的线段树套有序表过程中(其实就是归并排序的记录)

我们维护每个数在左右子区间中名次。

这样修改的时候我们只要对b[]排好序的整体做一次二分,找到b[m]<=x<b[m+1]

把修改成x当作修改成b[m],这样我们就能O(1)地更新每个子区间的计数,问题得解

  1 #include<bits/stdc++.h>
  2 #define mp make_pair
  3 using namespace std;
  4 const int mo=1000000007;
  5 vector< pair<int,int> > tr[100010*4];
  6 int laz[100010*4],s[100010*4],a[100010],b[100010],c[100010];
  7 int A,B,n,m,t;
  8 int C = ~(1<<31), M = (1<<16)-1;
  9 int rnd(int last,int &a,int &b)
 10 {
 11     a = (36969 + (last >> 3)) * (a & M) + (a >> 16);
 12     b = (18000 + (last >> 3)) * (b & M) + (b >> 16);
 13     return (C & ((a << 16) + b)) % 1000000000;
 14 }
 15
 16 void build(int i,int l,int r)
 17 {
 18     laz[i]=-2;
 19     tr[i].clear();
 20     if (l==r)
 21     {
 22         s[i]=(a[l]>=b[l]);
 23     }
 24     else {
 25         int m=(l+r)>>1;
 26         build(i*2,l,m);
 27         build(i*2+1,m+1,r);
 28         s[i]=s[i*2]+s[i*2+1];
 29         int x=l,y=m+1,h=l;
 30         while (x<=m&&y<=r)
 31         {
 32             if (b[x]<b[y])
 33             {
 34                 tr[i].push_back(mp(x-l,y-m-2));
 35                 c[h++]=b[x++];
 36             }
 37             else {
 38                 tr[i].push_back(mp(x-l-1,y-m-1));
 39                 c[h++]=b[y++];
 40             }
 41         }
 42         while (x<=m)
 43         {
 44             tr[i].push_back(mp(x-l,r-m-1));
 45             c[h++]=b[x++];
 46         }
 47         while (y<=r)
 48         {
 49             tr[i].push_back(mp(m-l,y-m-1));
 50             c[h++]=b[y++];
 51         }
 52         for (int k=l; k<=r; k++) b[k]=c[k];
 53     }
 54 }
 55
 56 void push(int i)
 57 {
 58     int x=laz[i];
 59     laz[i*2]=(x==-1)?-1:tr[i][x].first;
 60     laz[i*2+1]=(x==-1)?-1:tr[i][x].second;
 61     s[i*2]=laz[i*2]+1;
 62     s[i*2+1]=laz[i*2+1]+1;
 63     laz[i]=-2;
 64 }
 65
 66 void add(int i,int l,int r,int x,int y,int w)
 67 {
 68     if (x<=l&&y>=r)
 69     {
 70         laz[i]=w;
 71         s[i]=w+1;
 72     }
 73     else {
 74         int m=(l+r)>>1;
 75         if (laz[i]>-2) push(i);
 76         if (x<=m) add(i*2,l,m,x,y,w==-1?w:tr[i][w].first);
 77         if (y>m) add(i*2+1,m+1,r,x,y,w==-1?w:tr[i][w].second);
 78         s[i]=s[i*2]+s[i*2+1];
 79     }
 80 }
 81
 82 int ask(int i,int l,int r,int x,int y)
 83 {
 84     if (x<=l&&y>=r) return s[i];
 85     else {
 86         int m=(l+r)>>1,ans=0;
 87         if (laz[i]>-2) push(i);
 88         if (x<=m) ans+=ask(i*2,l,m,x,y);
 89         if (y>m) ans+=ask(i*2+1,m+1,r,x,y);
 90         return ans;
 91     }
 92 }
 93
 94 int main()
 95 {
 96     int cas;
 97     scanf("%d",&cas);
 98     while (cas--)
 99     {
100         scanf("%d%d%d%d",&n,&m,&A,&B);
101         for (int i=1; i<=n; i++) scanf("%d",&a[i]);
102         for (int i=1; i<=n; i++) scanf("%d",&b[i]);
103         b[n+1]=2147483647;
104         build(1,1,n);
105         int ans=0;
106         int last=0;
107         for (int i=1; i<=m; i++)
108         {
109             int l=rnd(last,A,B)%n+1,r=rnd(last,A,B)%n+1,x=rnd(last,A,B)+1;
110             if (l>r) swap(l,r);
111             if ((l+r+x)%2==0)
112             {
113                 last=ask(1,1,n,l,r);
114                 ans=(ans+1ll*i*last%mo)%mo;
115             }
116             else {
117                 int w=upper_bound(b+1,b+1+n,x)-b-2;
118                 add(1,1,n,l,r,w);
119             }
120         }
121         printf("%d\n",ans);
122     }
123 }

时间: 01-23

hdu5737的相关文章

hdu5737(2016多校联赛第2场D)

题意:给2组数据a和b数组,每次有2种操作:(+,l,r,x)把a数组第l个到第r个元素全置为x,(?,l,r)查询[l,r]之间哪些位置满足a[i]>=b[i](i>=l && i<=r)并把这些位置的数量统计 一直想很久,没想到什么有效的方案,直到看到题解才明白过来,原来线段树套平衡树还有这种情况:里面其实不是平衡树,只是有序表. 然后这题就转换为区间查找数对应排名 由于此题不用对2个数组都修改,其中1个b树可作为固定的线段树套有序表以节省时间,另外1个表a树则单纯使

HDU5737 : Differencia

注意到$b$不变,考虑用归并树来维护这个$b$序列,对于每个节点有序地维护$b$,同时在归并的时候预处理出每个元素在左右儿子里的排名. 在归并树上额外维护区间内$a\geq b$的个数以及赋值标记. 那么在区间赋值的时候,只需要在根节点的$b$数组中做一个二分,然后往下通过预处理的名次数组转移即可,标记下放时也是如此,每次转移复杂度显然是$O(1)$. 时间复杂度$O((n+m)\log n)$. #include<cstdio> #include<algorithm> const