云腾致雨

HDU 3244 完全背包 + 二分

发表于 2019-08-05 分类于 ACM题解

本以为是道简单的二分，WA到哭。

阅读全文 »

Machine Learning 离散化 + 带修改莫队

发表于 2019-08-02 分类于 ACM题解

题目链接

题意

给你一个序列，每次询问一个区间，问你区间内的Mex值。

什么是Mex值呢？比如说某个数字出现1次，某个数字出现3次，那么Mex就是：2.

这个类似于SG函数，就是未出现过的最小的那个数字。

另外输入中还会有另一种操作：单点修改

思路

我们肯定需要首先求出区间内每个数字出现的次数，然后再把这个次数存到一个数组中。求次数，不用说，莫队。但是单点修改需要用带修改莫队。需要注意的是，扩展区间的时候，要先扩展，再收缩，否则会出现下标为负数的情况。另外modify函数中，最后是交换两个数字，因为可能以后还得把他们换回来，所以不是赋值。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <math.h>
using namespace std;
const int maxn = 400005;
struct node{
   int l, r, id, pre;
  }q[maxn];

struct node1{
    int pos, val;
}C[maxn];

int num[maxn], ans[maxn], a[maxn], b[maxn << 2], col[maxn], sum[maxn];

bool cmp(node a , node b)
{
    if(col[a.l] != col[b.l])  return a.l < b.l;
    else if(col[a.r] != col[b.r]) return a.r < b.r;
    else  return a.pre < b.pre;
}

void update(int x, int add)
{
    ans[sum[x]]--;
    sum[x] += add;
    ans[sum[x]]++;
}

void modify(int time , int i)
{
    if(C[time].pos >= q[i].l && C[time].pos <= q[i].r)
    {
        update(a[C[time].pos], -1);
        update(C[time].val, 1);
    }
    swap(a[C[time].pos] ,C[time].val);
}

int main()
{
    int n, Q, op, ll, rr;
    scanf("%d %d",&n,&Q);
    int sz = pow(n, 0.67);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
        b[i] = a[i];
        col[i] = (i - 1)/ sz + 1;
    }
    int tot = 0, cnt = 0;
    for(int i = 1; i <= Q; ++i)
    {
        scanf("%d %d %d",&op, &ll, &rr);
        if(op == 1)
        {
            q[++tot].l = ll;
            q[tot].r = rr;
            q[tot].id = tot;
            q[tot].pre = cnt;
        }
        else{
            C[++cnt].pos = ll;
            C[cnt].val = rr;
            b[n + cnt] = rr;
        }
    }
    sort(q + 1, q + tot + 1, cmp);
    sort(b + 1, b + n + cnt + 1);
    int N = unique(b + 1, b + cnt + n + 1) - (b + 1);
    for(int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(b + 1, b + N + 1,a[i]) - b;
    }
    for(int i = 1; i <= cnt; ++i)
    {
        C[i].val = lower_bound(b + 1, b + N + 1, C[i].val) - b;
    }
    int l = 1, r = 0, time = 0;
    for(int i = 1; i <= tot; ++i)
    {
        while(l > q[i].l){l--; update(a[l], 1);}
        while(r < q[i].r){r++; update(a[r], 1);}
        while(r > q[i].r){update(a[r], -1); r--;}
        while(l < q[i].l){update(a[l], -1); l++;}
        while(time < q[i].pre){time++; modify(time, i);}
        while(time > q[i].pre){modify(time, i); time--;}
        int k = 1;
        while(ans[k]) k++;
        num[q[i].id] = k;
    }
    for(int i = 1; i <= tot; ++i)
    {
        cout << num[i] << '\n';
    }
}

HDU 4417 , 山东省赛Boring counting 主席树

发表于 2019-08-01 更新于 2019-08-07 分类于 ACM题解

题目链接

题意

求的是某一段区间内小于等于K的数字的个数。

思路

我们可以一开始输入的时候就把a[]和要询问的K存到一个b[]里，再求出a[]在b[]中的位置，建立n棵线段树，最后要求小于等于K的个数，实际上就是求第R棵线段树- 第L - 1棵线段树的那个线段树中区间端点的范围在1-K的总和。觉得这种方法很妙，大部分的题解都是用了二分。


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <queue>

using namespace std;
const int maxn = 100005;
struct node{
    int ls, rs, sum;
}tree[2500050];

int tot, a[maxn], b[2 * maxn], rt[maxn] , h[maxn],l[maxn],r[maxn];
void build(int &o , int l, int r)
{
    o = ++tot;
    tree[o].sum = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(tree[o].ls, l ,mid);
    build(tree[o].rs, mid + 1, r);
}

void update(int &o, int last, int l, int r, int pos)
{
    o = ++tot;
    tree[o].ls = tree[last].ls;
    tree[o].rs = tree[last].rs;
    tree[o].sum = tree[last].sum + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) update(tree[o].ls, tree[last].ls, l, mid, pos);
    else update(tree[o].rs, tree[last].rs, mid + 1, r, pos);
}

int Sum;
void query(int o, int last, int l ,int r, int left, int right)
{
    if(left > r || right < l) return;
    if(left <= l && r <= right)
    {
        Sum += tree[o].sum - tree[last].sum;
        return;
    }
    int mid = (l + r) >> 1;
    query(tree[o].ls, tree[last].ls, l, mid, left, right);
    query(tree[o].rs, tree[last].rs, mid + 1, r, left, right);
}
int main()
{
    int T,caser = 1;
    scanf("%d",&T);
    while(T--)
    {
        tot = 0;
        memset(tree, 0, sizeof(tree));
        int n,Q;
        scanf("%d %d",&n,&Q);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        for(int i = 1; i <= Q; ++i)
        {
            scanf("%d %d %d",&l[i],&r[i],&h[i]);
            b[n + i] = h[i];
        }
        sort(b + 1, b + n + Q + 1);
        int N = unique(b + 1, b + n + Q + 1) - (b + 1);
        build(rt[0], 1, N);
        for(int i = 1; i <= n; ++i)
        {
            a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b;
        }
        for(int i = 1; i <= n; ++i)
        {
            update(rt[i], rt[i - 1], 1, N, a[i]);
        }
        cout << "Case " << caser++ << ":" << '\n';
        for(int i = 1; i <= Q; ++i)
        {
            Sum = 0;
            int v = lower_bound(b + 1, b + N + 1, h[i]) - b;
            query(rt[r[i] + 1], rt[l[i]], 1, N, 1, v);
            printf("%d\n",Sum);
        }
    }
}

山东省第四届省赛

Boring counting

和上面的几乎一样了。


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <queue>

using namespace std;
const int maxn = 50005;
struct node{
     int ls, rs, sum;
}tree[maxn * 20];
int a[maxn], b[3 * maxn], rt[maxn],l[maxn], r[maxn] , k1[maxn], k2[maxn];
int tot, Sum;
void build(int &o, int l, int r)
{
    o = ++tot;
    tree[o].sum = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(tree[o].ls, l , mid);
    build(tree[o].rs, mid + 1, r);
}

void update(int &o, int last, int l, int r, int pos)
{
    o = ++tot;
    tree[o].ls = tree[last].ls;
    tree[o].rs = tree[last].rs;
    tree[o].sum = tree[last].sum + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid)  update(tree[o].ls, tree[last].ls, l, mid, pos);
    else  update(tree[o].rs, tree[last].rs, mid + 1, r, pos);
}

void query(int o, int last, int l, int r, int left, int right)
{
    if(left > r || right < l) return;
    if(left <= l && right >= r)
    {
        Sum += tree[o].sum  - tree[last].sum;
        return;
    }
    int mid = (l + r) >> 1;
    query(tree[o].ls, tree[last].ls, l, mid, left, right);
    query(tree[o].rs, tree[last].rs, mid + 1, r, left, right);
}

int main()
{
    int T,n,Q, caser = 1;
    scanf("%d",&T);
    while(T--)
    {
        tot = 0;
        scanf("%d %d",&n,&Q);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        int tot1 = n;
        for(int i = 1; i <= Q; ++i)
        {
            scanf("%d %d %d %d",&l[i],&r[i],&k1[i],&k2[i]);
            b[++tot1] = k1[i] - 1;
            b[++tot1] = k2[i];
        }
        sort(b + 1, b + tot1 + 1);
        int N = unique(b + 1, b + tot1 + 1) - (b + 1);
        build(rt[0], 1, N);
        for(int i = 1; i <= n; ++i)
        {
            a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b;
            update(rt[i], rt[i - 1], 1, N, a[i]);
        }
        printf("Case #%d:\n",caser++);
        for(int i = 1; i <= Q; ++i)
        {
            Sum = 0;
            int v = lower_bound(b + 1, b + N + 1,k1[i] - 1) - b;
            query(rt[r[i]], rt[l[i] - 1], 1, N, 1, v);
            int num1 = Sum;
            v = lower_bound(b + 1, b + N + 1, k2[i]) - b;
            Sum = 0;
            query(rt[r[i]], rt[l[i] - 1], 1, N, 1, v);
            printf("%d\n", Sum - num1);

        }
    }
}

Keen On Everything But Triangle 主席树 + 斐波那契

发表于 2019-07-31

比赛的时候想到用线段树存取每个区间前50大的数字，但是根本不知道怎么存，后来才知道用主席树，不用存，直接遍历50次查找前50大的就行！！白学了主席树了。。。

阅读全文 »

hdu 3333 离散化 + 莫队

发表于 2019-07-31 分类于 ACM题解

兴高采烈地准备巩固一下莫队算法，没想到又碰到了离散化，兴高采烈的交上去，没想到因为一个符号，WA了20分钟。

阅读全文 »

query SPOJ 莫队离线||在线主席树

发表于 2019-07-31 分类于 ACM题解

区间问题，很快就想到莫队，原来还能用主席树做，奇妙。

阅读全文 »

zoj 3772 线段树 + 矩阵乘法

发表于 2019-07-30 更新于 2019-08-19 分类于 ACM题解

乍一看觉得需要矩阵快速幂，但是还有区间询问的问题，所以需要用线段树+矩阵乘法。

对于任意的长度大于2的区间长度[L,R]的询问,有如下：

其中:

因此我们只需要用线段树维护区间内M（L+2）到M（R）的乘积，注意矩阵乘法的方向顺序。

因为query函数的问题，段错误N次. 还有注意数组的大小，太大也会段错误。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

typedef long long ll;
struct Matrix{
   ll m[4][4];
}tree[400005];
ll mod = 1000000007;

ll a[100005];
Matrix mul(Matrix a, Matrix b)
{
    Matrix tmp;
    memset(tmp.m,0,sizeof(tmp.m));
    for(int i = 1;i <= 2; ++i)
    {
        for(int j = 1; j <= 2; ++j)
        {
            for(int k = 1; k <= 2; ++k)
            {
                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
            }
        }
    }
    return tmp;
}

void build(int node, int l ,int r)
{
    if(l == r)
    {
        tree[node].m[1][1] = 1;
        tree[node].m[1][2] = a[l] % mod;
        tree[node].m[2][1] = 1;
        tree[node].m[2][2] = 0;
        return ;
    }
    int mid = (l + r) >> 1;
    build(node << 1, l ,mid);
    build(node << 1|1,mid + 1 , r);
    tree[node]= mul(tree[node << 1|1] , tree[node << 1]);
}

Matrix query(int node, int begin , int end, int l, int r)
{
    if(l <= begin && end <= r)
    {
        return tree[node];
    }
    int mid = (begin + end) >> 1;
    if(r <= mid)  return query(node << 1 , begin, mid, l , r);
    else if(l > mid ) return query(node << 1|1, mid + 1, end, l, r);
    else return mul(query(node << 1|1,mid + 1, end, l, r),query(node << 1,begin, mid, l, r));
}

int main()
{
    int T,n,Q;
    cin >> T;
    while(T--)
    {
        scanf("%d %d",&n,&Q);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lld",&a[i]);
        }
        build(1,1,n);
        while(Q--)
        {
            int L,R;
            scanf("%d %d",&L,&R);
            if(R - L < 2)
            {
                printf("%d\n",a[R] % mod);
            }
            else{
                Matrix c = query(1,1,n,L + 2, R);
                printf("%lld\n",(c.m[1][1] * a[L + 1] + c.m[1][2] * a[L]) % mod);
            }
        }
    }
}