题解 P4224 【简单数据结构】

s_r_f · 2019-01-26 23:23:46 · 题解

这是清华集训某天的T1吧。某神犇(反正不是我):T1送分的啊，暴力题啊

这题。。。。

题意:
每次在数列A的头/尾做一次操作(加数/删数)，每次求出"上升倍数子序列"的maxlen和cntfront.

一、忽略复杂度问题,先来想一个DP

由于我们求的是cntfront,所以状态当然要设计成:

  f[i]表示以i为开头的maxlen
  g[i][j]表示以i为开头,len = j的"上升倍数子序列"的nxt的个数。
  //实际上是 j > i 且 f[j] == j-1 的f[j]个数。
  //why?
  //主要是因为直接维护nxt非常麻烦,但是我们的dp中只要保留最优的转移方式。
  //而且如果一个nxt改了,复杂度直接就成了O(ans),
  //而新的状态是O(1)

每次操作之后dp.
(qty神犇:小数据dp什么g[][]啊,直接f[]就行了啊)
(但是g[][]是标算啊,先写上不然好烦啊)
这个转移很奇妙,每次枚举倍数/约数转移,跑的贼快！
于是我们就得到了n,q <= 1000 的 25pts! (连松一松都不要)

二、冷静分析

其实一开始第一眼看就觉得不可做,但是。。。题目条件好多啊！

之前的部分分一条性质都没用诶

我们冷静分析一下题目条件。

性质1.数列中的数有值域限制。
性质2.数列中没有相同的数值。
性质3.相同的数值只会被插入/删除不超过10次。

因为数列中没有相同的数值,
这个上升倍数子序列的A[i] >= A[i-1] * 2
因为A[i] <= 1000000, 2的20次方 = 1048576 > 1000000.
所以答案一定 < 20. 也就是说g数组不会爆空间！

再看看那个性质3。
枚举所有A[i]的倍数dp?

复杂度 = 10 × O(n + n/2 + n/3 + .. + 1)
= 10 × O(n) × O(1+1/2+1/3+1/4+...+1/n)
= 10 × O(n * H(n)) (H(n)表示调和级数)

≈ O(nlogn),比nlogn略大，不过暴力题,std肯定也得能过啊,否则...

枚举所有A[i]的倍数dp是10 * O(nlogn)的！
枚举所有A[i]的约数？O(nsqrt(n)).

好了,言归正传考虑每个操作吧。

首先我们定义一些变量:

f和g:不说了

fcnt[i] 表示f[j] = i的个数

pos[i] 表示i的位置(存在时唯一,不存在时设为0)

1、在开头add(x)

枚举x的所有倍数,直接求出x的g数组。
别忘了更新fcnt[],和pos[]。

  void Add_front(int x){
    int i;
    --l,a[l] = x,pos[x] = l;
    memset(g[l],0,sizeof(g[l])),f[l] = g[l][1] = 1;
    for (i = x<<1; i <= m; i += x) if (pos[i]) ++g[l][f[pos[i]] + 1];
    for (i = MAX - 1; i ; --i) if (g[l][i]) {f[l] = i,++fcnt[f[l]]; return;}
  }

2、开头del()

更新fcnt[]和pos[],直接把a[l]删除。

   void Del_front(){ --fcnt[f[l]],pos[a[l]] = 0,++l; }

3、结尾add(x) / del()

重点是讨论他们对于数列中a[r]的约数的dp的影响。

O(sqrt(n))枚举约数,然后从大到小更新。

upd:修改前应把f[]的原始值存进一个oldf[i]里，然后比对新的f[i]并决定是否修改。

细节说的比较多了,再没办法就只能看(copy)代码了:

    void DP_Add(int x,int ff){
        int i;
        ++fcnt[ff];
        for (i = 1; i <= Sqrt[x]; ++i) if (!(x % i)){
            if (pos[i] < pos[x]) ++g[pos[i]][ff+1];
            if (i * i != x && pos[x/i] < pos[x] && pos[x/i]) ++g[pos[x/i]][ff+1];
        }
    }
    void DP_Dev(int x,int ff){
        int i;
        --fcnt[ff];
        for (i = 1; i <= Sqrt[x]; ++i) if (!(x % i)){
            if (pos[i] && pos[i] < pos[x]) --g[pos[i]][ff+1];
            if (i * i != x && pos[x/i] < pos[x] && pos[x/i]) --g[pos[x/i]][ff+1];
        }
    }

好了,我们AC了本题！
放一下我丑陋的代码:

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0,f = 1; char c = getchar();
    while (c != EOF && !isdigit(c)) {if (c == '-') f = -1;c = getchar();}
    while (c != EOF && isdigit(c)) {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}
inline void write(int x){
    int k = 0;char put[40];
    if (!x) putchar('0');
    if (x < 0) putchar('-'),x = -x;
    while (x)  put[++k] = (x % 10) + '0',x /= 10;
    while (k)  putchar(put[k]),--k;
}

const int N = 100005 << 2,M = 1000005,Q = 100005,MAX = 21;

int n,m,q;
int a[N],l,r;

int fcnt[N]; 
int pos[M],f[N],g[N][MAX];

void Add_front(int x){
    int i;
    --l,a[l] = x,pos[x] = l;
    memset(g[l],0,sizeof(g[l])),f[l] = g[l][1] = 1;
    for (i = x<<1; i <= m; i += x) if (pos[i]) ++g[l][f[pos[i]] + 1];
    for (i = MAX - 1; i ; --i) if (g[l][i]) {f[l] = i,++fcnt[f[l]]; return;}
}
void Del_front(){ --fcnt[f[l]],pos[a[l]] = 0,++l; }

int Sqrt[M];
void DP_Add(int x,int ff){
    int i;
    ++fcnt[ff];
    for (i = 1; i <= Sqrt[x]; ++i) if (!(x % i)){
        if (pos[i] < pos[x]) ++g[pos[i]][ff+1];
        if (i * i != x && pos[x/i] < pos[x] && pos[x/i]) ++g[pos[x/i]][ff+1];
    }
}
void DP_Dev(int x,int ff){
    int i;
    --fcnt[ff];
    for (i = 1; i <= Sqrt[x]; ++i) if (!(x % i)){
        if (pos[i] && pos[i] < pos[x]) --g[pos[i]][ff+1];
        if (i * i != x && pos[x/i] < pos[x] && pos[x/i]) --g[pos[x/i]][ff+1];
    }
}

int c[N],len,oldf[N];

void Add_back(int x){
    ++r,a[r] = x,pos[x] = r;
    memset(g[r],0,sizeof(g[r])),f[r] = g[r][1] = 1,DP_Add(x,f[r]);

    int i,j;
    len = 0;
    for (i = 1; i <= Sqrt[x]; ++i) if (!(x%i)) ++len,c[len] = i,oldf[pos[i]] = f[pos[i]];
    for (i = Sqrt[x]; i >= 1; --i) if (i * i != x && !(x%i)) ++len,c[len] = x/i,oldf[pos[x/i]] = f[pos[x/i]];

    int id;
    for (i = len; i >= 1; --i) if (id = pos[c[i]]){
        for (j = MAX-1; j >= 0; --j) if (g[id][j]) {f[id] = j; break;}
        if (f[id] ^ oldf[id]) DP_Dev(c[i],oldf[id]),DP_Add(c[i],f[id]);
    }
}

void Del_back(){
    int i,j,x = a[r];

    DP_Dev(x,f[r]);
    len = 0;
    for (i = 1; i <= Sqrt[x]; ++i) if (!(x%i)) ++len,c[len] = i,oldf[pos[i]] = f[pos[i]];
    for (i = Sqrt[x]; i >= 1; --i) if (i * i != x && !(x%i)) ++len,c[len] = x/i,oldf[pos[x/i]] = f[pos[x/i]];
    int id;
    for (i = len; i >= 1; --i) if (id = pos[c[i]]){
        for (j = MAX-1; j >= 0; --j) if (g[id][j]) {f[id] = j; break;}
        if (f[id] ^ oldf[id]) DP_Dev(c[i],oldf[id]),DP_Add(c[i],f[id]);
    }
    f[r] = 0,pos[x] = 0,--r;
}

int b[N];
void Init(int n){
    int i;
    for (i = 1; i <= n; ++i) b[i] = read();
    for (i = 1; i <= n; ++i) Add_front(b[n-i+1]);
} 

int mxlen,_i;
void Answer(){
    for (_i = MAX - 1; _i ; --_i)
        if (fcnt[_i]) {write(_i),putchar(' '),write(fcnt[_i]),putchar('\n'); return;}
}

int main(){
    int i,op,x;
    n = read(),m = read(),q = read(),l = n + q + 50,r = l-1;
    for (i = 1; i <= m; ++i){
        Sqrt[i] = min(i,(int)sqrt(i) + 1);
        if (Sqrt[i] * Sqrt[i] > i) --Sqrt[i];
    }
    Init(n),Answer();
    while (q--){
        op = read();
        if (!op) x = read(),Add_front(x);
        else if (!(op^1)) x = read(),Add_back(x);
        else if (!(op^2)) Del_front();
        else Del_back();
        Answer();
    }
    return 0;
}

写在后面

看来这题还真的是个技巧题啊。。。
不过其实学过数论的同学发现整除和值域限制应该就很简单明显了吧。
所以说是个暴力题。
还是要再多多积累做题技巧啊。

题解完结。。