数据结构补充
P1972 [SDOI2009] HH的项链
求[l,r]区间中颜色的数量
#include<cstdio>
#include<algorithm>
#include<vector>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e6+5;
int c[N],ans,s;
int n,m,x,op,p[N],t[N],a[N],f[N],g[N];
int l[N],r[N];
vector<int> q[N],id[N];
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
x++;
while (x<N) {
c[x]+=y;
x+=lowbit(x);
}
}
int ask(int x){
x++;
s=0;
while (x){
s+=c[x];
x-=lowbit(x);
}
return s;
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]);
fo(i,1,n) {
p[i]=t[a[i]];
t[a[i]]=i;
}
scanf("%d",&m);
fo(i,1,m){
scanf("%d %d",&l[i],&r[i]);
q[r[i]].push_back(l[i]-1);
id[r[i]].push_back(i);
}
fo(i,1,n){
add(p[i],1);
f[i]=i;
// printf("%d\n",f[i]);
for (int j=0;j<(int)q[i].size();j++) {
g[id[i][j]]=ask(q[i][j]);
}
}
fo(i,1,m) {
ans=g[i]-f[l[i]-1];
printf("%d\n",ans);
}
return 0;
}
带修莫队
[国家集训队] 数颜色 / 维护队列
题目描述
墨墨购买了一套 \(N\) 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
-
\(Q\ L\ R\) 代表询问你从第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。
-
\(R\ P\ C\) 把第 \(P\) 支画笔替换为颜色 \(C\)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e6+5;
const int M=1e6+5;
int t,l[N],r[N],a[N],cnt[M],ans,n,m,pos[N],x,y;
int b[N],c[N],tot,z,d[N],e[N];
int o[N];
char op;
void R(int &x){
int a=0;char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
x=a;
}
struct node{
int l,r,t,id;
};
node q[N];
bool cmp(node a,node b){
if (a.l/t!=b.l/t) return a.l/t<b.l/t;
if (a.r/t!=b.r/t) return a.r/t<b.r/t;
return a.t<b.t;
}
inline void del(int x){
cnt[a[x]]--;
if (!cnt[a[x]]) ans--;
}
inline void add(int x){
cnt[a[x]]++;
if (cnt[a[x]]==1) ans++;
}
int main(){
// freopen("data.in","r",stdin);
R(n); R(m);
fo(i,1,n) R(a[i]);
fo(i,1,n) e[i]=a[i];
t=pow(n,1/3.0);
t=t*t;
tot=0;
scanf("\n");
fo(i,1,m) {
scanf("%c %d %d\n",&op,&x,&y);
if (op=='Q') {
z++;
q[z]=(node){x,y,tot,z};
}
else{
tot++;
b[tot]=x;
c[tot]=y;
d[tot]=e[x];
e[x]=y;
}
}
sort(q+1,q+z+1,cmp);
x=1; y=0; t=0; ans=0;
fo(i,1,z) {
while (x<q[i].l) del(x++);
while (y>q[i].r) del(y--);
while (x>q[i].l) add(--x);
while (y<q[i].r) add(++y);
while (t<q[i].t) {
t++;
if (x<=b[t] && b[t]<=y) del(b[t]);
a[b[t]]=c[t];
if (x<=b[t] && b[t]<=y) add(b[t]);
}
while (t>q[i].t) {
if (x<=b[t] && b[t]<=y) del(b[t]);
a[b[t]]=d[t];
if (x<=b[t] && b[t]<=y) add(b[t]);
t--;
}
o[q[i].id]=ans;
}
fo(i,1,z) printf("%d\n",o[i]);
return 0;
}
cdq分治
三维偏序
#include<bits/stdc++.h>
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (register int (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
const ll mo1=1e9+7;
const ll mo2=1e9+9;
const ll P=131;
const ll Q=13331;
const ll mo=998244353;
const int N=2e5+5;
int c[N],n,k,cnt[N];
ll f[N];
struct node{
int x,y,z,cnt,ans;
};
node a[N],b[N];
bool operator == (const node &a,const node &b){
return a.x==b.x && a.y==b.y && a.z==b.z;
}
bool cmp1(node a,node b){
if (a.x!=b.x) return a.x<b.x;
if (a.y!=b.y) return a.y<b.y;
return a.z<b.z;
}
bool cmp2(node a,node b){
if (a.y!=b.y) return a.y<b.y;
return a.z<b.z;
}
int lowbit(int x){
return x&(-x);
}
void upd(int x,int y){
for (;x<N;x+=lowbit(x)) c[x]+=y;
}
int ask(int x){
int s=0;
for (;x;x-=lowbit(x)) s+=c[x];
return s;
}
void solve(int l,int r){
if (l==r) return;
int m=(l+r)>>1;
solve(l,m); solve(m+1,r);
sort(a+l,a+m+1,cmp2);
sort(a+m+1,a+r+1,cmp2);
int i=l,j=m+1;
while (j<=r) {
while (i<=m && a[i].y<=a[j].y) {
upd(a[i].z, a[i].cnt);
i++;
}
a[j].ans+=ask(a[j].z);
j++;
}
fo(j,l,i-1) upd(a[j].z,-a[j].cnt);
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
//
scanf("%d %d",&n,&k);
fo(i,1,n) scanf("%d %d %d",&b[i].x, &b[i].y, &b[i].z);
sort(b+1,b+n+1,cmp1);
int tot=0;
for (int i=1,j;i<=n;i=j+1) {
j=i;
while (j<n && b[i]==b[j+1]) {
j++;
}
a[++tot]=b[i];
a[tot].cnt=j-i+1;
}
solve(1,tot);
fo(i,1,tot) f[a[i].ans+a[i].cnt-1]+=a[i].cnt;
fo(i,0,n-1) printf("%lld\n",f[i]);
return 0;
}
回滚莫队
歴史の研究
题面翻译
题目描述
JOI 教授决定用如下的方法分析这些日记：
-
选择日记中连续的几天 \([L,R]\) 作为分析的时间段；
-
定义事件 \(A\) 的重要度 \(W_A\) 为 \(A\times T_A\)，其中 \(T_A\) 为该事件在区间 \([L,R]\) 中出现的次数。
现在，您需要帮助教授求出所有事件中重要度最大的事件是哪个，并输出其重要度。
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;
struct Query {
int l, r, id;
} Q[N];
int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];
bool cmp(const Query& A, const Query& B) {
if (pos[A.l] == pos[B.l]) return A.r < B.r;
return pos[A.l] < pos[B.l];
}
void build() {
sz = sqrt(n);
tot = n / sz;
for (int i = 1; i <= tot; i++) {
L[i] = (i - 1) * sz + 1;
R[i] = i * sz;
}
if (R[tot] < n) {
++tot;
L[tot] = R[tot - 1] + 1;
R[tot] = n;
}
}
void Add(int v, ll& Ans) {
++cnt[v];
Ans = max(Ans, 1LL * cnt[v] * t[v]);
}
void Del(int v) { --cnt[v]; }
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> x[i], t[++m] = x[i];
for (int i = 1; i <= q; i++) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
build();
// 对询问进行排序
for (int i = 1; i <= tot; i++)
for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
sort(Q + 1, Q + 1 + q, cmp);
// 离散化
sort(t + 1, t + 1 + m);
m = unique(t + 1, t + 1 + m) - (t + 1);
for (int i = 1; i <= n; i++) x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;
int l = 1, r = 0, last_block = 0, __l;
ll Ans = 0, tmp;
for (int i = 1; i <= q; i++) {
// 询问的左右端点同属于一个块则暴力扫描回答
if (pos[Q[i].l] == pos[Q[i].r]) {
for (int j = Q[i].l; j <= Q[i].r; j++) ++__cnt[x[j]];
for (int j = Q[i].l; j <= Q[i].r; j++)
ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);
for (int j = Q[i].l; j <= Q[i].r; j++) --__cnt[x[j]];
continue;
}
// 访问到了新的块则重新初始化莫队区间
if (pos[Q[i].l] != last_block) {
while (r > R[pos[Q[i].l]]) Del(x[r]), --r;
while (l < R[pos[Q[i].l]] + 1) Del(x[l]), ++l;
Ans = 0;
last_block = pos[Q[i].l];
}
// 扩展右端点
while (r < Q[i].r) ++r, Add(x[r], Ans);
__l = l;
tmp = Ans;
// 扩展左端点
while (__l > Q[i].l) --__l, Add(x[__l], tmp);
ans[Q[i].id] = tmp;
// 回滚
while (__l < l) Del(x[__l]), ++__l;
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}