对于询问(a,b)，设X=(数列中小于等于b的数字和),Y=b*(数列中大于b的数字的个数),若X+Y>=a*b，则询问可行，否则不可行，实现的话用两个树状数组维护一下即可

　　代码

　　

1 #include
     
       2 #include
      
        3 #include
       
         4 #define fi first 5 #define sc second 6 #define mp make_pair 7 #define N 2000100 8 using namespace std; 9 long long c1[N],c2[N],e[N],a[N],b[N];10 int typ[N],n,i,m,tot,u,v[N];11 char ch;12 int ef(int x)13 {14     int l=1,r=n,m;15     while (l<=r)16     {17         m=(l+r)>>1;18         if (e[m]>x) r=m-1;else l=m+1;19     }20     return r;21 }22 int lowbit(int x)23 {24     return x&-x;25 }26 void cc(int x,int w,long long ww)27 {28     while (x<=n)29     {30         c1[x]+=w;31         c2[x]+=ww;32         x+=lowbit(x);33     }34 }35 pair
        
          sum(int x)36 {37     int ans1=0;38     long long ans2=0;39     while (x)40     {41         ans1+=c1[x];42         ans2+=c2[x];43         x-=lowbit(x);44     }45     return mp(ans1,ans2);46 }47 int main()48 {49     scanf("%d%d",&n,&m);50     tot++;e[tot]=0;51     for (i=1;i<=m;i++)52     {53         scanf(" %c %lld%lld",&ch,&a[i],&b[i]);54         if (ch=='U') 55         {56             tot++;e[tot]=b[i];57             typ[i]=0;58         }59         else typ[i]=1;60     }61     sort(e+1,e+1+tot);e[0]=-1;n=0;62     for (i=1;i<=tot;i++)63     if (e[i]!=e[i-1]) e[++n]=e[i];64     cc(1,n,n*e[1]);65     for (i=1;i<=m;i++)66     {67         if (!typ[i])68         {69             u=ef(v[a[i]]);70             cc(u,-1,-v[a[i]]);71             v[a[i]]=b[i];72             u=ef(v[a[i]]);73             cc(u,1,v[a[i]]);74         }75         else76         {77             u=ef(b[i]);78             pair
         
           ans2=sum(u);79             long long v1=n-ans2.fi;80             long long v2=ans2.sc;81             if (v1*b[i]+v2>=a[i]*b[i])82             printf("TAK\n");83             else84             printf("NIE\n");85         }86     }87 }