HDU 5997 rausen loves cakes

预处理加树状数组进行优化

题目链接HDU 5997

题目大意

给你一个数组，数组中的数代表颜色，有两种操作，一是将数组中的X替换为Y，二是查询数组的某一子区间[x,y]中有多少段颜色。

题目解析

本题对时间要求较高。常规操作会超时，因此需要优化操作。
有多种优化。最初我只优化了修改操作，建立一个map表，并不真正修改数组中的值，而是直接map[x]=y，查询时取数组中的map值即可，但这种操作需要循环遍历整个数组来判断颜色段数，因此超时。之后我想到用树状数组来优化查询操作，动态维护树状数组b[]，若节点i产生颜色变化,则节点i的值设为1，则update(i,1),因此查询时只需要sum[y]-sum[x]+1即可得到颜色段数。但当修改时，仍然需要for循环遍历，将某个位置的颜色x改为颜色y时，对不同的情况进行不同的维护操作。但仍然超时。后来受到同伴的启发，我们可以开个map>，提前记录某个颜色的所有位置，将for循环遍历改为启发式的vector遍历，就能压着时间线过了。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define maxn 100010
using namespace std;
int a[maxn];
int n,q;
int b[maxn];//树状数组
int lowbit(int x)
{
        return x & (-x);
}
void  update(int i,  int x)
{
        while (i <= n)
        {
                b[i] = b[i] + x;
                i += lowbit(i);
        }
}
int sum(int i)
{
        int  ans = 0;
        while (i > 0)
        {
                ans += b[i];
                i -= lowbit(i);
        }
        return ans;
}
map<int,vector<int> > mp;//启发式，记录某个颜色的位置
map<int,vector<int> >::iterator itt;
vector<int>::iterator it;
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
                mp.clear();
                scanf("%d %d",&n,&q);
                memset(b,0,sizeof(b));
                for(int i=1;i<=n;i++)
                {
                        scanf("%d",&a[i]);
                        if(a[i]!=a[i-1])//将产生颜色变化的位置记录为1
                        {
                                update(i,1);
                        }
                        mp[a[i]].push_back(i);//记录某个颜色的位置
                }
                while(q--)
                {
                        int op,x,y;
                        scanf("%d %d %d",&op,&x,&y);
                        if(op==1&x!=y)
                        {

                                for(it=mp[x].begin();it!=mp[x].end();it++)
                                {
                                        int i=*it;//根据情况维护树状数组
                                        if(x==a[i-1]&&y!=a[i-1])
                                        {
                                                update(i,1);
                                        }
                                        else if(x!=a[i-1]&&y==a[i-1])
                                        {
                                                update(i,-1);
                                        }
                                        if(x==a[i+1]&&y!=a[i+1])
                                        {
                                                update(i+1,1);
                                        }
                                        else if(x!=a[i+1]&&y==a[i+1])
                                        {
                                                update(i+1,-1);
                                        }
                                        a[i]=y;
                                        mp[y].push_back(i);//维护map
                                }
                                mp[x].clear(); //维护map
                        }
                        else if(op==2)
                        {
                                int ans=sum(y)-sum(x)+1;
                                printf("%d\n",ans);
                        }
                }
        }
        return 0;
}