20190709 暑训区间种类数

ゞ浴缸里的玫瑰 2021-11-29 11:58 153阅读 0赞

## [I - Turing Tree][] [HDU - 3333 ][HDU - 3333] ##

这个题目求的不是区间种类数，而是求一个区间不同数加和。

这个题目第一次碰到感觉有点难，看了题解，就是首先对这个区间进行离散化，然后对于每一个查询区间对r进行排序。

为什么要对 r 进行排序呢， 笼统的说就是消去前面更新对后面的影响。

举个例子， 1 1 2 1 3  如果查询区间是 3 5， 1 4， 1 2 ，那么排完序之后就是  1 2，1 4，3 5

查 1 2 的之前就可以把第一个1删去，第二个1 就放到第二个位置，查1 4 是不受影响的，查4 之前会把第三个和第四个放进去，然后第2个又会被删除，

第四个又会放进去，。。。

[推荐博客 ][Link 1] 这个讲的很清楚。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <stack>
    #include <iostream>
    #include <map>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 1e5 + 10;
    typedef long long ll;
    ll sum[maxn * 8];
    int a[maxn], b[maxn], vis[maxn];
    struct node
    {
        int l, r, id;
        ll ans;
    }ex[maxn];
    
    bool cmp1(node a,node b)
    {
        return a.r < b.r;
    }
    
    bool cmp2(node a,node b)
    {
        return a.id < b.id;
    }
    
    void push_up(int id)
    {
        sum[id] = sum[id << 1] + sum[id << 1 | 1];
        //printf("sum[%d]=%lld\n", id, sum[id]);
    }
    
    void update(int id,int l,int r,int pos,int val)
    {
        if(l==r)
        {
            sum[id] = val;
        //    printf("  sum[%d]=%d\n", id, val);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos, val);
        else update(id << 1 | 1, mid + 1, r, pos, val);
        push_up(id);
    }
    
    ll query(int id,int l,int r,int x,int y)
    {
        if(x<=l&&y>=r) return sum[id];
        int mid = (l + r) >> 1;
        ll ans = 0;
        if (x <= mid) ans += query(id << 1, l, mid, x, y);
        if (y > mid) ans += query(id << 1 | 1, mid + 1, r, x, y);
        return ans;
    }
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            int n, m;
            scanf("%d", &n);
            memset(sum, 0, sizeof(sum));
            for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
            sort(b + 1, b + 1 + n);
            int len = unique(b + 1, b + 1 + n) - b - 1;
            for(int i=1;i<=n;i++)
            {
                a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
            }
            scanf("%d", &m);
            for (int i = 1; i <= m; i++) scanf("%d%d", &ex[i].l, &ex[i].r), ex[i].id = i;
            sort(ex + 1, ex + 1 + m, cmp1);
            memset(vis, 0, sizeof(vis));
            int k = 1;
            for(int i=1;i<=n;i++)
            {
                if(vis[a[i]])
                {
                    update(1, 1, n, i, b[a[i]]);
                    update(1, 1, n, vis[a[i]], 0);
                    vis[a[i]] = i;
                }
                else
                {
                    update(1, 1, n, i, b[a[i]]);
                    vis[a[i]] = i;
                }
                //printf("a[%d]=%d b[%d]=%d\n", i, a[i], a[i], b[a[i]]);
                while(i==ex[k].r&&k<=m)
                {
                    ex[k].ans = query(1, 1, n, ex[k].l, ex[k].r);
                    k++;
                }
            }
            sort(ex + 1, ex + 1 + m, cmp2);
            for (int i = 1; i <= m; i++) printf("%lld\n", ex[i].ans);
        }
        return 0;
    }

线段树

# [区间种类数][Link 2] #

这个和上面那个很类似，基本上是一样的。

这个可以用莫队来写，顺便学习了一下莫队。

图灵数的莫队代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <string>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 1e5 + 10;
    typedef long long ll;
    int a[maxn], b[maxn], pos[maxn], vis[maxn];
    ll ans[maxn], Ans;
    struct node
    {
        int l, r, id;
    }ex[maxn];
    
    bool cmp(node a,node b)
    {
        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
    }
    
    void add(int x)
    {
        if (!vis[a[x]]) Ans += b[a[x]];
        ++vis[a[x]];
    }
    
    void del(int x)
    {
        --vis[a[x]];
        if (!vis[a[x]]) Ans -= b[a[x]];
    }
    
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            Ans = 0;
            memset(vis, 0, sizeof(vis));
            int n, m;
            scanf("%d", &n);
            int siz = sqrt(n);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
                b[i] = a[i];
                pos[i] = i / siz;
            }
            sort(b + 1, b + n + 1);
            int len = unique(b + 1, b + 1 + n) - b - 1;
            for(int i=1;i<=n;i++)
            {
                a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
            }
            scanf("%d", &m);
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d", &ex[i].l, &ex[i].r);
                ex[i].id = i;
            }
            sort(ex + 1, ex + 1 + m, cmp);
            int l = 1, r = 0;
            for(int i=1;i<=m;i++)
            {
                int ql = ex[i].l, qr = ex[i].r;
                while (l < ql) del(l), l++;
                while (l > ql) l--, add(l);
                while (r < qr) r++, add(r);
                while (r > qr) del(r), r--;
                ans[ex[i].id] = Ans;
            }
            for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
        }
        return 0;
    }

莫队

接下来写几个莫队的基本题目：

[E. XOR and Favorite Number][][  https://codeforces.com/contest/617/problem/E][E. XOR and Favorite Number]

这个题目的意思是让你求一个区间的异或值等于k的数有多少，

莫队基本上是套板子，只有add 和del 函数要自己写。

这个异或首先我们可以求前缀异或和，sum\[i\]  然后因为 a^b=c 可得 a^c=b

所以我们要一段区间 sum\[i\]^sum\[j\]=k  可以变成sum\[i\]^k=sum\[j\]

知道这一点了就好写多了，

这个add  ans+=vis\[a\[i\]^k\]  ++vis\[a\[i\]\]

这个del  ans-=vis\[a\[i\]^k\]    --vis\[a\[i\]\]

这个上面都是看题解的，但是为什么这个题目可以用莫队写呢，首先这个不强制在线，

其次觉得我们是要求一个区间满足条件的数，区间和满足条件的数的个数。

这个一般就可以用到莫队，具体还是多写写题目，刷点感觉吧

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <map>
    #include <string>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 1e5 + 10;
    const int maxn1 = 1e7 + 10;
    typedef long long ll;
    int a[maxn], pos[maxn], vis[maxn1];
    ll ans[maxn], Ans;
    int n, m, k;
    int l, r;
    struct node
    {
        int l, r, id;
    }ex[maxn];
    
    bool cmp(node a,node b)
    {
        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
    }
    
    void add(int x)
    {
        
        Ans += vis[a[x] ^ k];//这个先统计答案再加上这个，不重复加。这个顺序主要是解决a[x]^k=a[x]，其他情况下先加哪个都一样。
        ++vis[a[x]];
        // printf("a[%x]=%d k=%d\n", x, a[x], k);
        // printf("add l=%d r=%d x=%d Ans=%lld %d\n",l,r, x, Ans,a[x]^k);
    }
    
    void del(int x)
    {
        --vis[a[x]];//先减去这个点，可以理解为求种类，先减去这个点，如果减去之后这个点不存在了，种类就-1
        Ans -= vis[a[x] ^ k];//这个同理，如果减去这个点之后，这个ans就要减去和这个成对的数，如果恰好是其本身
        //设未减去时为x，这个时候和他成对的应该只有x-1了。
        // printf("del l=%d r=%d x=%d Ans=%lld\n",l,r ,x, Ans);
    }
    
    
    int main()
    {
        vis[0] = 1;
        scanf("%d%d%d", &n,&m,&k);
        int siz = sqrt(n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            a[i] ^= a[i - 1];
            pos[i] = i / siz;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d", &ex[i].l, &ex[i].r);
            ex[i].id = i;
        }
        sort(ex + 1, ex + 1 + m, cmp);
        l = 0, r = 0;
        for(int i=1;i<=m;i++)
        {
            int ql = ex[i].l, qr = ex[i].r;
            // printf("ql=%d qr=%d\n", ql, qr);
            while (l <= ql) del(l), l++;
            while (l >= ql) l--, add(l);
            while (r < qr) r++, add(r);
            while (r > qr) del(r), r--;
            ans[ex[i].id] = Ans;
            // printf("Ans=%lld\n", Ans);
        }
        for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
        return 0;
    }

莫队

[BZOJ2038][]

注意开long long

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <map>
    #include <string>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 1e5 + 10;
    const int maxn1 = 1e7 + 10;
    typedef long long ll;
    int a[maxn], pos[maxn], vis[maxn];
    ll Ans;
    struct node
    {
        int l, r, id;
        ll ans;
    }ex[maxn];
    
    bool cmp(node a,node b)
    {
        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
    }
    
    bool cmp1(node a,node b)
    {
        return a.id < b.id;
    }
    
    void add(int x)
    {
        Ans += vis[a[x]];
        ++vis[a[x]];
        //printf("add x=%d Ans=%d vis[%d]=%d\n", x, Ans, a[x], vis[a[x]]);
    }
    
    void del(int x)
    {
        --vis[a[x]];
        Ans -= vis[a[x]];
        //printf("del x=%d Ans=%d vis[%d]=%d\n", x, Ans, a[x], vis[a[x]]);
    }
    
    ll gcd(ll a,ll b)
    {
        return b == 0 ? a : gcd(b, a%b);
    }
    
    int main()
    {
        int n, m;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            Ans = 0;
            memset(vis, 0, sizeof(vis));
            int sz = sqrt(n);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
                pos[i] = i / sz;
            }
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d", &ex[i].l, &ex[i].r);
                ex[i].id = i;
            }
            sort(ex + 1, ex + 1 + m, cmp);
            int l = 1, r = 0;
            for(int i=1;i<=m;i++)
            {
                int ql = ex[i].l, qr = ex[i].r;
                while (l < ql) del(l), l++;
                while (l > ql) l--, add(l);
                while (r > qr) del(r), r--;
                while (r < qr) r++, add(r);
                ex[i].ans = Ans;
            }
            sort(ex + 1, ex + 1 + m, cmp1);
            for(int i=1;i<=m;i++)
            {
                ll len = ex[i].r - ex[i].l + 1;
                ll un = len * (len - 1) / 2;
                ll g = gcd(un, ex[i].ans);
                printf("%lld/%lld\n", ex[i].ans / g, un / g);
            }
        }
        return 0;
    }

莫队

[D. Powerful array][]

这个题目也很好写，没什么思维量，如果你可以意识到这个是一个莫队了就应该可以很快的写出来。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <map>
    #include <string>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 1e6 + 10;
    const int maxn1 = 1e7 + 10;
    typedef long long ll;
    ll a[maxn], pos[maxn], vis[maxn1];
    struct node
    {
        int l, r, id;
    }ex[maxn];
    ll Ans, ans[maxn];
     
    bool cmp(node a,node b)
    {
        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
    }
     
    void add(int x)
    {
    //    printf("x=%d\n", x);
        Ans -= vis[a[x]] * vis[a[x]] * a[x];
        ++vis[a[x]];
        Ans += vis[a[x]] * vis[a[x]] * a[x];
    }
     
    void del(int x)
    {
        Ans -= vis[a[x]] * vis[a[x]] * a[x];
        --vis[a[x]];
        Ans += vis[a[x]] * vis[a[x]] * a[x];
    }
     
    int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        int sz = sqrt(n);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &ex[i].l, &ex[i].r);
            pos[i] = i / sz;
            ex[i].id = i;
        }
        sort(ex + 1, ex + 1 + m, cmp);
        int l = 1, r = 0;
        for(int i=1;i<=m;i++)
        {
            int ql = ex[i].l, qr = ex[i].r;
            //printf("ql=%d qr=%d\n", ql, qr);
            while (l < ql) del(l), l++;
            while (l > ql) l--, add(l);
            while (r < qr) r++, add(r);
            while (r > qr) del(r), r--;
            ans[ex[i].id] = Ans;
        }
        for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
        return 0;
    }

莫队

## [Lucky][]  [HDU - 5213 ][HDU - 5213] ##

这个题目没有之前那么简单，这个题，需要用到一点点的容斥定理来解决多区间询问问题。

我们要找  从(l1,r1)找到一个x，再从(l2,r2)找到一个y，使得x+y==k 问这样的有多少对。

这个是多区间的，莫队无法直接解决，所以就想办法转化成单区间的。

从(l1,r1) 和 （l2,r2) 各找一个 相当于在 (l1,r2）中找到若干对，然后 减去 （l1,l2) 再减去 （r1,r2) 再加上 (r1,l2） 的

这个被减去的都是不符合要求的。

ans=f ( l1 , r2 ) - f( l1 , l2 ) - f ( r1 , r2 ) + f ( r1 , l2 )

这个方法还挺巧妙的。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <map>
    #include <string>
    #include <iostream>
    #define inf 0x3f3f3f3f
    #define inf64 0x3f3f3f3f3f3f3f3f
    using namespace std;
    const int maxn = 3e5 + 10;
    const int maxn1 = 1e7 + 10;
    typedef long long ll;
    ll a[maxn], pos[maxn];
    ll ans[maxn], Ans, vis[maxn];
    int n, k, m;
    struct node
    {
        int l,r, id;
        int f;
    }ex[maxn];
    
    bool cmp(node a,node b)
    {
        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
    }
    
    void add(int x)
    {
        if (a[x] < k) Ans += vis[k - a[x]];
        ++vis[a[x]];
    }
    
    void del(int x)
    {
        --vis[a[x]];
        if (a[x] < k) Ans -= vis[k - a[x]];
    }
    
    
    int main()
    {
        while(scanf("%d%d",&n,&k)!=EOF)
        {
            Ans = 0;
            memset(vis, 0, sizeof(vis));
            memset(ans, 0, sizeof(ans));
            int sz = sqrt(n), tot = 0;
            for (int i = 1; i <= n; i++) {
                scanf("%lld", &a[i]);
                pos[i] = i / sz;
            }
            scanf("%d", &m);
            for(int i=1;i<=m;i++)
            {
                int l1, l2, r1, r2;
                scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
                ex[++tot].l = l1, ex[tot].r = r2, ex[tot].f = 1, ex[tot].id = i;
                ex[++tot].l = l1, ex[tot].r = l2 - 1, ex[tot].f = -1, ex[tot].id = i;
                ex[++tot].l = r1 + 1, ex[tot].r = r2, ex[tot].f = -1, ex[tot].id = i;
                ex[++tot].l = r1 + 1, ex[tot].r = l2 - 1, ex[tot].f = 1, ex[tot].id = i;
            }
            sort(ex + 1, ex + 1 + tot, cmp);
            int l = 0, r = 0;
            for(int i=1;i<=tot;i++)
            {
                int ql = ex[i].l, qr = ex[i].r;
                while (l < ql) del(l), l++;
                while (l > ql) l--, add(l);
                while (r < qr) r++, add(r);
                while (r > qr) del(r), r--;
                ans[ex[i].id] += Ans * 1ll * ex[i].f;
            }
            for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
        }
        return 0;
    }

莫队

转载于:https://www.cnblogs.com/EchoZQN/p/11212350.html

[I - Turing Tree]: https://vjudge.net/problem/HDU-3333
[HDU - 3333]: https://vjudge.net/problem/15630/origin
[Link 1]: https://blog.csdn.net/calculate23/article/details/87701266
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211129/df63007a6aec4881ba20e8105ae9d140.png
[Link 2]: http://www.fjutacm.com/Problem.jsp?pid=3097
[E. XOR and Favorite Number]: https://codeforces.com/contest/617/problem/E
[BZOJ2038]: https://www.lydsy.com/JudgeOnline/problem.php?id=2038
[D. Powerful array]: https://codeforces.com/problemset/problem/86/D
[Lucky]: https://vjudge.net/problem/HDU-5213
[HDU - 5213]: https://vjudge.net/problem/158722/origin