有哪些游戏网站,永久开源的免费建站系统,在线看视频网站怎么做,郑州专业做网站的P1972 [SDOI2009]HH的项链
题意#xff1a;
给你一个序列#xff0c;问这个序列中的种类数 n,m,ai1e6
题解#xff1a;
三个方法#xff1a;莫队(会超时)#xff0c;树状数组#xff0c;主席树(会超时)
莫队就是裸题#xff0c;不讲了#xff0c;复杂度O(n*sq…P1972 [SDOI2009]HH的项链
题意
给你一个序列问这个序列中的种类数 n,m,ai1e6
题解
三个方法莫队(会超时)树状数组主席树(会超时)
莫队就是裸题不讲了复杂度O(n*sqrt(n))
树状数组 对于若干个区间[l,r]如果他们的r都相等那么项链中出现的同一个数字一定只关心最右边的那一个。 比如1 3 4 5 1 对于r5的所有询问第一个位置上的1是没有价值的因为第五个位置已经出现1也就是对于所有查询[L,5]区间来说如果第一个1被算那么它完全可以用第5个1来代替 因此我们对所有询问按照r来排序然后维护一个树状数组。 树状数组的用途 对于序列1 2 1 3 我们用pre[i]来表示上一此出现i的位置 对于第一个1insert(1,1),此时树状数组表示的每个数有1 0 0 0 对于第二个2insert(2,1),此时1 1 0 0 对于第三个1因为之前出现过1所以将之前1的位置删掉insert(1,-1),然后再把当前1加入insert(3,1).此时就是0 1 1 0 询问[2,3]就是sum(3)-sum(2-1)2
主席树做法 对于每个点我们用nex表示这个点之后最近的颜色相同的点的位置如果没有就设为n1. 对于区间询问l~r之间的种类其实就是求满足(lirnex[i]r)的个数因为如果某个点的next已近超出了这个区间的范围就说明这个点对答案产生贡献了(其实和树状数组思想是一样的相同颜色只考虑离r最近的) 这样问题就变成在区间l~r之间权值大于r的个数 复杂度是O(mlogn),也会超时
代码
莫队
// Problem: P1972 [SDOI2009]HH的项链
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1972
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Data:2021-08-12 09:19:00
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
template typename T inline void read(T x)
{T f 1;x 0;char ch getchar();while (0 isdigit(ch)) {if (ch -)f -1;ch getchar();}while (0 ! isdigit(ch))x (x 1) (x 3) ch - 0, ch getchar();x* f;
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
int n, m;
const int maxn 3e6 9;
int a[maxn];
int block;
struct node
{int l, r;int id;bool operator(const node x) const{if (l / block ! x.l / block)return l x.l;if ((l / block) 1)return r x.r; // 注意这里和下面一行不能写小于大于等于否则会出错详见下面的小细节return r x.r;}
} q[maxn];
int ans[maxn];
int vis[maxn];
int tot 0;
void add(int x)
{vis[a[x]];if (vis[a[x]] 1)tot;
}
void del(int x)
{vis[a[x]]--;if (vis[a[x]] 0)tot--;
}// bool cmp(node a, node b)
// {
// if (a.r / block b.r / block)
// return a.l b.l;
// return a.r b.r;
// }
int main()
{//rd_test();read(n);block sqrt(n);for (int i 1; i n; i)read(a[i]);read(m);for (int i 1; i m; i) {read(q[i].l);read(q[i].r);q[i].id i;}sort(q 1, q 1 m);int l 1, r 0;for (int i 1; i m; i) {int L q[i].l, R q[i].r;while (l L)del(l);while (l L)add(--l);while (r R)add(r);while (r R)del(r--);ans[q[i].id] tot;}for (int i 1; i m; i) {printf(%d\n, ans[i]);}return 0;//Time_test();
}
树状数组
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
template typename T inline void read(T x)
{T f 1;x 0;char ch getchar();while (0 isdigit(ch)) {if (ch -)f -1;ch getchar();}while (0 ! isdigit(ch))x (x 1) (x 3) ch - 0, ch getchar();x* f;
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e6;
int a[maxn];
struct node
{int l, r;int id;
} q[maxn];
int sum[maxn];
int ans[maxn];
int n;
int vis[maxn];
bool cmp(node a, node b)
{return a.r b.r;
}
int lowbit(int x)
{return x (-x);
}
void add(int pos, int x)
{for (int i pos; i n; i lowbit(i)) {sum[i] x;}
}
int query(int pos)
{int ans 0;for (int i pos; i 1; i- lowbit(i)) {ans sum[i];}return ans;
}
int query(int l, int r)
{return query(r) - query(l - 1);
}
int main()
{//rd_test();read(n);for (int i 1; i n; i)read(a[i]);int m;read(m);for (int i 1; i m; i)read(q[i].l), read(q[i].r), q[i].id i;sort(q 1, q 1 m, cmp);int beg 1;for (int i 1; i m; i) {for (int j beg; j q[i].r; j) {if (vis[a[j]])add(vis[a[j]], -1);add(j, 1);vis[a[j]] j;}beg q[i].r 1;ans[q[i].id] query(q[i].l, q[i].r);}for (int i 1; i m; i)printf(%d\n, ans[i]);return 0;//Time_test();
}
主席树
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
template typename T inline void read(T x)
{T f 1;x 0;char ch getchar();while (0 isdigit(ch)) {if (ch -)f -1;ch getchar();}while (0 ! isdigit(ch))x (x 1) (x 3) ch - 0, ch getchar();x* f;
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e6 9;
int rs[maxn], ls[maxn];
int sum[maxn];
int n;
int a[maxn];
int rt[maxn];
int tot 0;
int vis[maxn], nex[maxn];
void build(int o, int l, int r)
{o tot;sum[o] 0;if (l r)return;int mid (l r) 1;build(ls[o], l, mid);build(rs[o], mid 1, r);
}
void update(int o, int l, int r, int nex, int p)
{o tot;ls[o] ls[nex];rs[o] rs[nex];sum[o] sum[nex] 1;if (l r)return;int mid (l r) 1;if (p mid)update(ls[o], l, mid, ls[nex], p);elseupdate(rs[o], mid 1, r, rs[nex], p);
}
int query(int u, int v, int l, int r, int k)
{int mid (l r) 1;int ans 0;if (l r) {return sum[v] - sum[u];}if (k mid) {int x sum[rs[v]] - sum[rs[u]];ans query(ls[u], ls[v], l, mid, k) x;}elseans query(rs[u], rs[v], mid 1, r, k);return ans;
}
int main()
{//rd_test();read(n);for (int i 1; i n; i) {read(a[i]);if (vis[a[i]])nex[vis[a[i]]] i;vis[a[i]] i;}for (int i 1; i n; i) {if (!nex[i])nex[i] n 1;}build(rt[0], 1, n 1);for (int i 1; i n; i) {int p nex[i];update(rt[i], 1, n 1, rt[i - 1], p);}int m;read(m);while (m--) {int l, r;read(l), read(r);printf(%d\n, query(rt[l - 1], rt[r], 1, n 1, r 1));}//Time_test();
}
