P4113 [HEOI2012]采花 (莫队TLE)

思路

update 11.2 树状数组ＡＣ

本题莫队过不去，会TLE

但也是个不错的莫队练手题

毕竟Chen_Zhe还给了100分莫队分（还会给你小对勾）

莫队＆＆树状数组代码

// luogu-judger-enable-o2

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 2e6 + 7;

int n, m, a[maxn], sum[maxn << 1];

struct edge {

    int size,las1,las2;

} zz[maxn];

int ans[maxn];

struct node {

    int s, t,id;

    bool operator < (const node b ) const {

        return t < b.t;

    }

} b[maxn];

int read() {

    int x = 0, f = 1; char s = getchar();

    for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;

    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

    return x * f;

}

int lowbit(int x) {

    return x & -x;

}

void add(int x, int dat) {

    for (; x <= n; x += lowbit(x))

        sum[x] += dat;

}

int query(int x) {

    int ans = 0;

    for (; x >= 1; x -= lowbit(x))

        ans += sum[x];

    return ans;

}

int main() {

    n = read();

    m = read();

    m=read();

    for (int i = 1; i <= n; ++i)

        a[i] = read();

    for (int i = 1; i <= m; ++i)

        b[i].s = read(), b[i].t = read(), b[i].id = i;

    sort(b + 1, b + 1 + m);

    int js = 1;

    for (int i = 1; i <= n; ++i) {

        if(!zz[a[i]].size) {

            zz[a[i]].las1=i;

        } else {

            if(zz[a[i]].size>=2)

                add(zz[a[i]].las2,-1);

            add(zz[a[i]].las1,1);

            swap(zz[a[i]].las1,zz[a[i]].las2);

            zz[a[i]].las1=i;

        }

        ++zz[a[i]].size;

        if(b[js].t==i) {

            int end_ans=query(b[js].t);

            for(; b[js].t==i; ++js) {

                ans[b[js].id]=end_ans-query(b[js].s-1);

            }

        }

    }

    for (int i = 1; i <= m; ++i) {

        printf("%d\n", ans[i]);

    }

    return 0;

}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define maxn 	2000007

using namespace std;

inline int read()

{

    int x=0,f=1;char s=getchar();

    while('0'>s||s>'9') {

        if(s=='-') f=-1;

        s=getchar();

    }

    while('0'<=s&&s<='9') {

        x=x*10+s-'0';

        s=getchar();

    }

    return x*f;

}

int n,m,k,now;

int a[maxn];

int belong[maxn];

int vis[maxn];

int ans[maxn];

struct node{

	int l,r,id;

}q[maxn];

inline bool cmp(const node &a,const node &b)

{

	return belong[a.l]==belong[b.l] ? a.r<b.r :  belong[a.l]<belong[b.l];

}

inline void Add(int x)

{

	vis[x]==1 ? ++now : now;

	++vis[x];

}

inline void Delet(int x)

{

	vis[x]==2 ? --now : now;

	--vis[x];

}

int main()

{

	n=read();

	int meiyongdebianliang_qidaotixingfanweidezuoye__233zhemechangdebianliangming=read();

	m=read();

	k=sqrt(n);

	for(int i=1;i<=n;++i)

		a[i]=read();

	for(int i=1;i<=n;++i)

		belong[i]=(i-1)/k+1;

	for(int i=1;i<=m;++i)

	{

		q[i].l=read();

		q[i].r=read();

		q[i].id=i;

	}

	sort(q+1,q+1+m,cmp);

	int l=1,r=0;

	for(int i=1;i<=m;++i)

	{

		while(l > q[i].l) Add(a[--l]);

		while(l < q[i].l) Delet(a[l++]);

		while(r < q[i].r) Add(a[++r]);

		while(r > q[i].r) Delet(a[r--]);

		ans[q[i].id]=now;

	}

	for(int i=1;i<=m;++i)

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

P4113 [HEOI2012]采花 (莫队TLE)

思路

update 11.2 树状数组ＡＣ

本题莫队过不去，会TLE

但也是个不错的莫队练手题

毕竟Chen_Zhe还给了100分莫队分（还会给你小对勾）

莫队＆＆树状数组代码

最新文章

热门文章

巴特西

P4113 [HEOI2012]采花 (莫队TLE)

思路

update 11.2 树状数组ＡＣ 本题莫队过不去，会TLE

但也是个不错的莫队练手题

毕竟Chen_Zhe还给了100分莫队分 （还会给你小对勾）

莫队＆＆树状数组代码

最新文章

热门文章

update 11.2 树状数组ＡＣ

本题莫队过不去，会TLE

毕竟Chen_Zhe还给了100分莫队分（还会给你小对勾）