CSU-ACM2020寒假集训比赛2

A - Messenger Simulator

两种解法，我选择了第二种

mn很好求，联系过就是1，没联系过就是初始位置

第一种:统计同一个人两次联系之间的出现的不同的人的个数，这个值用来更新mx[i]，模拟一下就可以理解。而在第一次联系之前的部分，由于初始是顺序的，所以只需要统计i第一次联系之前出现的大于i的不同的人的个数，用这个数字和初始位置之和来更新mx[i]。对于最后一次联系之后的部分，我们可以假定在m+1的位置再次与其进行联系，然后套用前面两次联系之间的情况即可，需要注意的是对于所有的i都是假设在m+1的位置再次进行联系。对于从来都没有联系过的人，同样假设m+1联系并套用第一次联系之前的模式即可，其实也就是整个序列m中比i大的不同人的个数是多少。复杂度在统计两次联系之间那里，可以用莫队或者主席树实现，其他部分可以用树状数组实现。

第二种就是模拟这个过程，初始位置对应线段树m+1~m+n区间，每次练习就是把一个人当前位置对应权值-1，然后在最前面+1，容易发现只需要统计每次联系前的位置即可(仍视为m+1次联系了所有的i，其实就是在全部联系结束之后再次统计当前位置)。

 #include<bits/stdc++.h>

 #define LL long long

 #define dl double

 using namespace std;

 const int inf=3e5+;

 int n,m;

 int mn[inf],mx[inf];

 int f[inf<<];

 int fir,hs[inf];

 #define mid (l+r>>1)

 #define rs  (o<<1|1)

 #define ls  (o<<1)

 void add(int o,int l,int r,int x,int y){

  if(l == r){f[o]+=y;return ;}

  if(x <= mid)add(ls,l,mid,x,y);

  else add(rs,mid+,r,x,y);

  f[o]=f[ls]+f[rs];

 }

 int query(int o,int l,int r,int x){

  if(r <= x)return f[o];

  if(x <= mid)return  query(ls,l,mid,x);

  else return f[ls]+query(rs,mid+,r,x);

 }

 int main(){

 // freopen("in.txt","r",stdin);

  scanf("%d%d",&n,&m);fir=m;

  for(int i=;i<=n;i++)add(,,n+m,hs[i]=i+m,),mx[i]=mn[i]=i;

  for(int i=;i<=m;i++){

   int x;scanf("%d",&x);

   mx[x]=max(mx[x],query(,,n+m,hs[x]));

   add(,,n+m,hs[x],-);

   add(,,n+m,hs[x]=fir--,);

   mn[x]=;

  }

  for(int i=;i<=n;i++)mx[i]=max(mx[i],query(,,n+m,hs[i]));

  for(int i=;i<=n;i++)printf("%d %d\n",mn[i],mx[i]);

  return ;

 }

B - Restore Permutation

CodeForces - 1208D

此题很容易想到从后往前处理。最后一个可以直接算出来，然后排除他的影响，算倒数第二个....我们需要证明一个结论，对于当前处理的位置(排除了已经用过的)，s[i]严格单调，此结论很容易证明，任取i<j即可发现s[i]<s[j]。我开了一个set储存当前剩余的元素，set内比较的是其在当前位置时对应的s[i]，然后lower_bound即可找到答案，nlog^2。

标答1的解法是:每次寻找s[i]为0的点，最右面的这种点便是1(他的右面不可能有0了)，然后把他后面的s[i]都-1，再找2，重复此过程。

标答2是树状数组做法，同样倒序处理，巧妙运用树状数组免去了二分的麻烦同时省去了"删除操作"，也就把我的set直接去掉了。

 #include<bits/stdc++.h>

 #define LL long long

 #define dl double

 using namespace std;

 const int inf=2e5+;

 int n;

 LL s[inf];

 LL f[inf];

 int a[inf];

 int lowbit(int x){return x&(-x);}

 LL sum(int x){LL ans=;for(int i=x;i;i-=lowbit(i))ans+=f[i];return ans;}

 void add(int x){for(int i=x;i<=n;i+=lowbit(i))f[i]+=x;}

 struct ghb{

  int id;

  LL val;

  bool operator < (const ghb &o)const{

   LL tp1=1ll*id*(id-)/-sum(id),tp2=1ll*o.id*(o.id-)/-sum(o.id);

   if(!o.id)tp2=o.val;

   return tp1 < tp2;

  }

 };

 set<ghb>S;

 set<ghb>::iterator g;

 int main(){

 // freopen("in.txt","r",stdin);

  scanf("%d",&n);

  for(int i=;i<=n;i++)scanf("%lld",&s[i]),S.insert((ghb){i,});

  for(int i=n;i>=;i--){

   g=S.lower_bound((ghb){,s[i]});

   a[i]=(*g).id;add((*g).id);S.erase(g);

  }

  for(int i=;i<=n;i++)printf("%d ",a[i]);

  return ;

 }

C - Turing Tree

HDU - 3333

莫队的模板题

或者还有两种解法

第一种:主席树，在线算法，每个位置记录对应数值上一次出现的位置，然后变成了区间查询小于l的元素个数的问题，只不过是把权值1变成了对应数的数值。

另一种:线段树/树状数组，离线算法，把询问按右节点排序，依次插入每一个数，在树状数组中加上对应值，如果这个数之前出现过，那么把之前的减去对应值。

 #include<bits/stdc++.h>

 #define LL long long

 #define dl double

 using namespace std;

 const int inf=3e4+;

 int T;

 int n,m;

 struct ghb{

  int id,val1,val2;

  bool operator < (const ghb &o)const{return val1 < o.val1;}

 }a[inf];

 bool cmp1(ghb &a,ghb &b){return a.id < b.id;}

 int bel[inf];

 struct Query{

  int l,r,id;

  LL ans;

  bool operator < (const Query &o)const{return bel[l] == bel[o.l] ? r<o.r : bel[l]<bel[o.l];}

 }q[inf<<];

 bool cmp2(Query &a,Query &b){return a.id < b.id;}

 int cnt[inf];

 void work(){

  LL ans=;

  int l=,r=;

  for(int i=;i<=m;i++){

   while(l < q[i].l){

    cnt[a[l].val2]--;

    if(cnt[a[l].val2] == )ans-=a[l].val1;

    l++;

   }

   while(l > q[i].l){

    l--;

    cnt[a[l].val2]++;

    if(cnt[a[l].val2] == )ans+=a[l].val1;

   }

   while(r < q[i].r){

    r++;

    cnt[a[r].val2]++;

    if(cnt[a[r].val2] == )ans+=a[r].val1;

   }

   while(r > q[i].r){

    cnt[a[r].val2]--;

    if(cnt[a[r].val2] == )ans-=a[r].val1;

    r--;

   }

   q[i].ans=ans;

  }

 }

 int main(){

 // freopen("in.txt","r",stdin);

  scanf("%d",&T);

  a[].val1=-;

  while(T--){

   memset(cnt,,sizeof(cnt));

   scanf("%d",&n);int len=sqrt(n);

   for(int i=;i<=n;i++)scanf("%d",&a[i].val1),bel[a[i].id=i]=(i-)/len+;

   sort(a+,a+n+);

   for(int i=;i<=n;i++)a[i].val2=a[i].val1 == a[i-].val1 ? a[i-].val2 : a[i-].val2+;

   sort(a+,a+n+,cmp1);

   scanf("%d",&m);

   for(int i=;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;

   sort(q+,q+m+);

   work();

   sort(q+,q+m+,cmp2);

   for(int i=;i<=m;i++)printf("%lld\n",q[i].ans);

  }

  return ;

 }

 /*莫队模板题*/

D - Welfare State

CodeForces - 1199D

第一感觉就是线段树模拟这个过程，因为只有一次询问所以也不是吉司机那种，然后写的过程中发现有些累赘，感觉有更简单的方法。

其实可以用O(n)的做法，只要倒序枚举所有操作并记录2操作最大值，在某个位置的1操作第一次被枚举到的时候更新当前点的值即可，同样，从来没被1操作过的可以视为在0处有一个1操作，也就是全枚举完后对没被1操作过的位置取一个max。

只有线段树的代码

 #include<bits/stdc++.h>

 #define LL long long

 #define dl double

 using namespace std;

 const int inf=2e5+;

 int n,q;

 int f[inf<<],tag[inf<<];

 #define ls (o<<1)

 #define rs (o<<1|1)

 #define mid (l+r>>1)

 void tagdown(int o){

  tag[ls]=max(tag[ls],tag[o]);

  tag[rs]=max(tag[rs],tag[o]);

  tag[o]=;

 }

 void modify(int o,int l,int r,int x,int y){

  if(l == r){tag[o]=;f[o]=y;return ;}

  tagdown(o);

  if(x <= mid)modify(ls,l,mid,x,y);

  else modify(rs,mid+,r,x,y);

 }

 void out(int o,int l,int r){

  if(l == r){printf("%d ",max(f[o],tag[o]));return ;}

  tagdown(o);out(ls,l,mid);out(rs,mid+,r);

 }

 int main(){

 // freopen("in.txt","r",stdin);

  scanf("%d",&n);

  for(int i=;i<=n;i++){int x;scanf("%d",&x);modify(,,n,i,x);}

  scanf("%d",&q);

  for(int i=;i<=q;i++){

   int x,y,z;scanf("%d%d",&x,&y);

   if(x == ){scanf("%d",&z);modify(,,n,y,z);}

   else tag[]=max(tag[],y);

  }

  out(,,n);

  return ;

 }

 /*又是一道伪吉司机线段树，因为只有一次询问所以很简单*/

 /*似乎压根不存在f的转移，应该可以用更简洁的方法做出来*/

E - Playlist

CodeForces - 1140C

道理很简单，按b从大到小排序，顺序枚举选择前k大。然而我选择了很愚蠢的二分+树状数组来求前k大，事实上一个优先队列就可以轻松解决。

 #include<bits/stdc++.h>

 #define LL long long

 #define dl double

 using namespace std;

 const int inf=3e5+;

 int n,k;

 struct Song{

  int t,b;

  bool operator < (const Song &o)const{

   return b > o.b;

  }

 }a[inf];

 int lowbit(int x){return x&(-x);}

 int f1[inf<<];

 LL f2[inf<<];

 void add(int x){int y=1e6-x+;for(int i=y;i<=1e6;i+=lowbit(i))f1[i]++,f2[i]+=x;}

 int sum1(int x){int ans=;for(int i=x;i;i-=lowbit(i))ans+=f1[i];return ans;}

 LL  sum2(int x){LL  ans=;for(int i=x;i;i-=lowbit(i))ans+=f2[i];return ans;}

 LL ANS;

 int main(){

 // freopen("in.txt","r",stdin);

  scanf("%d%d",&n,&k);

  for(int i=;i<=n;i++)scanf("%d%d",&a[i].t,&a[i].b);

  sort(a+,a+n+);

  for(int i=;i<=n;i++){

   add(a[i].t);

   int l1=,r1=1e6;

   while(l1 != r1){

    int mid=(l1+r1>>)+;

    if(sum1(mid) > k)r1=mid-;

    else l1=mid;

   }

   int l2=,r2=1e6;

   while(l2 != r2){

    int mid=l2+r2>>;

    if(sum1(mid) < k)l2=mid+;

    else r2=mid;

   }

   LL ans=sum2(l1);

   int tp1=sum1(l1);

   if(tp1 < k && sum1(l2) > k)ans+=1ll*(1e6-l2+)*(k-tp1);

   ANS=max(ANS,ans*a[i].b);

  }

  printf("%lld\n",ANS);

  return ;

 }

 /*二分+树状数组实现前k大?*/

巴特西