1. 题目

传送门= ̄ω ̄=

2. 题解

我做这题的历程:

  1. 普通线段树套平衡树(map),70分
  2. 半递归式(修改变为递推)线段树套平衡树(map),80分
  3. 树状数组套平衡树(map),90分
  4. 树状数组套哈希表(pbds,cc_hash_table),90分
  5. 树状数组套哈希表(pbds,gp_hash_table),AC

心累啊。

具体做法很暴力,就是对于树状数组的每个节点搞个哈希表存某种编码出现的次数。

查询和修改就和普通的树状数组一模一样。

代码很短。

代码:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define lowbit(a) (a&-a)
using namespace std;
using namespace __gnu_pbds;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
int n,m,data[100005];
char opt[5];
gp_hash_table<int,int> mp[100005];
void update(int pos,int k,int d){while(pos<=n)mp[pos][k]+=d,pos+=lowbit(pos);}
int query(int pos,int k)
{
    int sum=0;
    while(pos)sum+=mp[pos][k],pos-=lowbit(pos);
    return sum;
}
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)IN(data[i]),update(i,data[i],1);
    int a,b,c;
    while(m--)
    {
        scanf("%s",opt),IN(a),IN(b);
        if(opt[0]=='Q')IN(c),printf("%d\n",query(b,c)-query(a-1,c));
        else update(a,b,1),update(a,data[a],-1),data[a]=b;
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *