网站开发项目教程答案,建筑设计公司取名字大全集,刷抖音一天赚四五百块,我们高清中国免费观看传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的数列aaa#xff0c;有qqq个询问#xff0c;每次询问[l,r][l,r][l,r]中值域在[a,b][a,b][a,b]中的数出现的次数和在[a,b][a,b][a,b]中出现过的数值个数。 n≤1e5,1≤a≤1e5n\le1e5,1\le…传送门 文章目录题意思路题意
给你一个长度为nnn的数列aaa有qqq个询问每次询问[l,r][l,r][l,r]中值域在[a,b][a,b][a,b]中的数出现的次数和在[a,b][a,b][a,b]中出现过的数值个数。
n≤1e5,1≤a≤1e5n\le1e5,1\le a \le 1e5n≤1e5,1≤a≤1e5
思路
这个题可以值域分块来写经典模型了。
这里介绍cdqcdqcdq的写法考虑分的三维是那三维。
比较容易想到前两维是l≤pos≤r,a≤val≤bl\le pos\le r,a\le val\le bl≤pos≤r,a≤val≤b第二个答案的统计是难点考虑如何统计第二个答案。记pre[val]pre[val]pre[val]代表valvalval之前出现的位置我们如果能知道有多少0≤pre[val]≤l−10\le pre[val]\le l-10≤pre[val]≤l−1是不是就可以了因为[a,b][a,b][a,b]中的每个值的preprepre在[0,l−1][0,l-1][0,l−1]最多出现一次所以我们第三维就是这个
并不是不能忽略的一个很重要的问题就是cdqcdqcdq需要保证先进行修改再进行查询所以第三维应该保证修改在查询之前与pre[val]pre[val]pre[val]是多少无关因为第一第二维已经定序。
这里给一组hackhackhack样例
2 1
2 2
1 2 2 2
当然这是对于不离散化来说的如果你离散化了那么就另当别论了。
复杂度O(nlog2n)O(nlog^2n)O(nlog2n)
// Problem: P4396 [AHOI2013]作业
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4396
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
#define lowbit(x) ((x)(-x))
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N6000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N],pre[N],tot;
struct Node {int x,y,z,op,id,val;
}q[N],p[N];
vectorintv;bool cmp(Node a,Node b) {if(a.x!b.x) return a.xb.x;else if(a.y!b.y) return a.yb.y;else return a.opb.op;}int tr[N],ans[N],ans1[N];void add(int x,int c) {for(int ix;iN;ilowbit(i)) tr[i]c;
}int sum(int x) {int ans0;for(int ix;i;i-lowbit(i)) anstr[i];return ans;
}void cdq(int l,int r) {if(lr) return;int mid(lr)1;cdq(l,mid); cdq(mid1,r);int il,jmid1;int now0,cnt0;while(imidjr) {// if(l1r3q[i].yq[j].y) {// coutq[i].op q[j].op**endl;// } if(q[i].yq[j].y) {p[now]q[i];if(q[i].op0) {add(q[i].z1,1);cnt;}i;} else {p[now]q[j];if(q[j].op1) {ans[q[j].id]sum(q[j].z1)*q[j].val;ans1[q[j].id]cnt*q[j].val;}j;}}while(imid) {p[now]q[i];if(q[i].op0) {add(q[i].z1,1);cnt;}i;}while(jr) {p[now]q[j];if(q[j].op1) {ans[q[j].id]sum(q[j].z1)*q[j].val;ans1[q[j].id]cnt*q[j].val;}j;}for(int il;imid;i) if(q[i].op0) add(q[i].z1,-1);for(int il,j1;ir;i,j) q[i]p[j];
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;in;i) {int x; scanf(%d,x);a[i]x; v.pb(x);}v.pb(0);sort(v.begin(),v.end());for(int i1;in;i) {int x; xa[i];q[tot]{i,x,pre[x],0,0,0};pre[x]i;}for(int i1;im;i) {int l,r,a,b; scanf(%d%d%d%d,l,r,a,b);q[tot]{r,b,l-1,1,i,1};q[tot]{l-1,a-1,l-1,1,i,1};q[tot]{l-1,b,l-1,1,i,-1};q[tot]{r,a-1,l-1,1,i,-1};}sort(q1,q1tot,cmp);cdq(1,tot);for(int i1;im;i) printf(%d %d\n,ans1[i],ans[i]);return 0;
}
/*
lxr
avalb
0posl-1x y z op val0 1 0 1 1
0 2 0 1 -1
1 2 0 0 02 1 0 1 -1
2 2 0 1 1
2 2 1 0 00 1 0 1 1
0 2 0 1 -1
1 2 0 0 0
2 1 0 1 -1
2 2 0 1 1
2 2 1 0 0*/
