题目链接

题目大意

令两个序列为 $k$ -相似，当且仅当 $k$

$k$ 为两个序列对应位置上不同的值的个数，例如1 2 3 4与1 3 3 3为2-相似，因为两个序列2位置与4位置是不同的。现有一个长度为

n n $n$ 的序列，可以将它划分为长度为

L

$L$ 的

n−L+1 n − L + 1 $n-L+1$ 个子串。

Q Q $Q$ 组询问，求每个子串与多少个其他子串为

\leq k_{i}

$\leq k_i$ 相似。

$L\leq n\leq 10^4,Q\leq 10^2$ ，空间32MB。

题解

考虑不卡空间的做法，令f[i][j]表示 $i$ 子串与其他子串有多少个 $j$

$j$ -相似的。转移时枚举两个子串开始位置的间隔，若开始位置+1，那么相似-原开始位置是不是相同的+新结束位置是不是相同的。最后前缀和求

≤j ≤ j $\leq j$ 的和

现在考虑卡空间的做法，如果询问的是2,6,8，那么一个子串与另一个子串4-相似，实际上只会对询问6,8产生影响，离线存下所有询问，修改操作就直接找到第一个 $\geq$ 它的询问，在询问上面修改，最后还是前缀和。

代码

#include 
   
    #include 
    
     int read(){    int x=0,f=1;    char ch=getchar();    while((ch<'0')||(ch>'9'))    {        if(ch=='-')        {            f=-f;        }        ch=getchar();    }    while((ch>='0')&&(ch<='9'))    {        x=x*10+ch-'0';        ch=getchar();    }    return x*f;}int print(int x){    if(x<0)    {        putchar('-');        x=-x;    }    if(x/10)    {        print(x/10);    }    putchar('0'+x%10);    return 0;}const int maxn=10000;const int maxq=100;struct query{    int val,pre_id,ans_id;    bool operator <(const query &other) const    {        return val

转载地址：http://abwo.baihongyu.com/

你可能感兴趣的文章