Gym101350 FMonkeying Around

题意

有n只猴子排成一排，一共有m个笑话。开始时，这些猴子都坐在椅子上。下面m行给出的每个笑话包含三个整数x,l,k。代表猴子x讲了笑话l，所以距离x小于等于k的猴子如果他们从没听过这个笑话，他们会掉下椅子，如果听过这个笑话他们会爬回椅子上。问在讲完m个笑话以后，还有哪些猴子是还坐在椅子上的。

分析

当时在场上想到了是线段树，但是总是想保存下每个猴子听每个笑话听了几遍，发现数组都开不下，很难受。。

我们来看大佬们的想法：

对于每只猴子，它是在椅子上还是在地上只取决于它听到的最后一个笑话一共听了几遍。

所以我们首先要找出每只猴子听到的最后一个笑话是什么，然后再找出这个笑话他听了几遍。

我们可以想到用两颗线段树分别求这两个东西。第一颗线段树是比较好想的，关键是第二颗。

假设我们现在已经知道了每只猴子听到的最后一个笑话是什么。

对于每个笑话，我们在一颗线段树上做，做完以后删除。然后统计最后一个听到的笑话是这个的人的听的次数。这样遍历笑话和猴子，均摊是O（n）的，线段树的操作是logn（这段话来自大佬：https://www.cnblogs.com/huibixiaoxing/p/7678842.html，感谢指点）

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <vector>

 using namespace std;

 const int maxn=+;

 int T,n,m;

 struct Node{

     int l,r,num;

 }node[maxn];

 int x,l,k;

 int set[*maxn],num[maxn];

 void pushdown(int o){

     if(set[o]){

         set[*o]=set[o];

         set[*o+]=set[o];

         set[o]=;

     }

 }

 int ql,qr,c;

 void update(int o,int L,int R){

     if(ql<=L&&qr>=R){

         set[o]=c;

         return;

     }

     pushdown(o);

     int M=L+(R-L)/;

     if(ql<=M)

     update(*o,L,M);

     if(qr>M)

     update(*o+,M+,R);

     return ;

 }

 int ask(int o,int L,int R,int p){

     if(L==R){

         return set[o];

     }

     pushdown(o);

     int M=L+(R-L)/;

     if(p<=M)

         return ask(*o,L,M,p);

     else

         return ask(*o+,M+,R,p);

 }

 //*******以下是第二棵线段树

 int sum[*maxn],addv[*maxn];

 void pushdown2(int o){

     if(addv[o]){

         addv[*o]+=addv[o];addv[*o+]+=addv[o];

         sum[*o]+=addv[o];sum[*o+]+=addv[o];

         addv[o]=;

     }

     return ;

 }

 void update2(int o,int L,int R){

     if(ql<=L&&qr>=R){

         addv[o]+=c;

         sum[o]+=c;

         return ;

     }

     pushdown2(o);

     int M=L+(R-L)/;

     if(ql<=M)

         update2(*o,L,M);

     if(qr>M)

         update2(*o+,M+,R);

     return;

 }

 int ask2(int o,int L,int R,int p){

     if(L==R)return sum[o];

     int M=L+(R-L)/;

     pushdown2(o);

     if(p<=M)

         return ask2(*o,L,M,p);

     else

         return ask2(*o+,M+,R,p);

 }

 struct Interval{

     int l,r;

 };

 vector<Interval>V1[maxn];

 vector<int>V2[maxn];

 int M,ans;

 int main(){

     scanf("%d",&T);

     for(int t=;t<=T;t++){

         M=-,ans=;

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

         for(int i=;i<maxn;i++)V1[i].clear();

         for(int i=;i<maxn;i++)V2[i].clear();

         memset(set,,sizeof(set));

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

             scanf("%d%d%d",&x,&l,&k);

             node[i].l=max(,x-k);

             node[i].r=min(n,x+k);

             node[i].num=l;

             M=max(M,node[i].num);

             V1[node[i].num].push_back((Interval){node[i].l,node[i].r});

             ql=node[i].l,qr=node[i].r,c=node[i].num;

             update(,,n);

         }

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

             int g=ask(,,n,i);

            // cout<<i<<" "<<g<<endl;

             V2[g].push_back(i);

         }

         memset(sum,,sizeof(sum));

         memset(addv,,sizeof(addv));

     /*    for(int i=1;i<=M;i++){

             printf("%d :",i);

             for(int j=0;j<V2[i].size();j++){

                 printf("%d ",V2[i][j]);

             }

             printf("\n");

         }*/

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

           //  cout<<i<<endl;

             for(int j=;j<V1[i].size();j++){

                 Interval inter=V1[i][j];

                 ql=inter.l,qr=inter.r,c=;

                 update2(,,n);

             }

             for(int j=;j<V2[i].size();j++){

                 if(ask2(,,n,V2[i][j])>=){

                    // printf("%d %d\n",V2[i][j],ask2(1,1,n,V2[i][j]));

                     ans++;

                 }

             }

             for(int j=;j<V1[i].size();j++){

                 Interval inter=V1[i][j];

                 ql=inter.l,qr=inter.r,c=-;

                 update2(,,n);

             }

         }

         printf("%d\n",ans);

     };

 return ;

巴特西

Gym101350 FMonkeying Around

最新文章

热门文章