http://codeforces.com/contest/387

E题

贪心+树状数组。
很明显,从最小的开始删除得到的香肠最多。做个位置标记,然后往set里面加要留下的数(从小到大)的位置值,并对每一个要删除的数(这个不加到set中)求出其往左往右能到达的位置值,然后用树状数组统计这一区间有多少个没有删除的数,即为得到的香肠数。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 936 ms, 40384 KB */
const int mx = int(1e6) + 5;

int n, tree[mx];
void U(int pos, int val) {for (; pos <= n; pos += pos & -pos) tree[pos] += val;}
int sum(int pos) {int sum = 0; for (; pos; pos &= pos - 1) sum += tree[pos]; return sum;}
inline int Q(int st, int en) {return sum(en) - sum(st);}

int pos[mx];
bool has[mx];
set<int> s;

int main()
{
    int m, i, x;
    ll ans = 0;
    siter itx, ity;
    SII(n, m);
    s.insert(0), s.insert(n + 1);
    Forr(i, 1, n + 1) SI(x), pos[x] = i, U(i, 1);
    while (m--) SI(x), has[x] = true;
  
    Forr(i, 1, n + 1)
    {
        if (has[i]) s.insert(pos[i]);
        else
        {
            itx = ity = s.upper_bound(pos[i]);
            ans += Q(*--itx, *ity - 1);
            U(pos[i], -1);
        }
    }
    PL(ans);
    return 0;
}

Comments

comments powered by Disqus