精华内容
下载资源
问答
  • 港真我不知道原题是怎么回事儿,上了离散化,后来无论是d-query还是路边的蒲公英好像完全没必要上离散化,毕竟是1e5个数字,开个数组记录下就行了,所以这部分删掉,然后模拟一下我们查询区间众数出现次数的方法,...

    2020.5.19
    昨天学完莫队之后重写了一遍mcpc19的那一道区间众数的,发现了几个可以改进的点。一个是离散化,港真我不知道原题是怎么回事儿,上了离散化,后来无论是d-query还是路边的蒲公英好像完全没必要上离散化,毕竟是1e5个数字,开个数组记录下就行了,所以这部分删掉,然后模拟一下我们查询区间众数出现次数的方法,首先考虑加入坐标位置为x,数字为a[x],对于当前区间维护的答案的影响,首先要消除对于上一次a[x]出现的影响,那就是sum[cnt[a[x]]] -1, 然后将出现次数cnt[a[x]]加一,比较其与目前出现次数的的大小,然后将sum[cnt[a[x]]] 加一,就完成了一次维护,缩进的del函数同理,就是看sum[cnt[a[x]]] 是不是为0,如果cnt[a[x]]是目前最大次数,(因为sum[cnt[a[x]]] 是0所以是唯一最大次数),那么就对答案进行-1,修正后的区间就是我们所需要的答案。
    代码如下:

    #include <bits/stdc++.h>
    using namespace std;
    #define limit (10000 + 5)//防止溢出
    #define INF 0x3f3f3f3f
    #define inf 0x3f3f3f3f3f
    #define lowbit(i) i&(-i)//一步两步
    #define EPS 1e-6
    #define FASTIO  ios::sync_with_stdio(false);cin.tie(0);
    #define ff(a) printf("%lld\n",a );
    #define pi(a,b) pair<a,b>
    #define rep(i, a, b) for(int i = a ; i <= b ; ++i)
    #define per(i, a, b) for(int i = b ; i >= a ; --i)
    #define mint(a,b,c) min(min(a,b), c)
    #define MOD 998244353
    #define FOPEN freopen("C:\\Users\\administrator01\\CLionProjects\\untitled24\\data.txt", "rt", stdin)
    typedef long long ll;
    typedef unsigned long long ull;
    ll read(){
        ll sign = 1, x = 0;char s = getchar();
        while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}
        while(s >= '0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}
        return x * sign;
    }//快读
    void write(ll x){
        if(x / 10) write(x / 10);
        putchar(x % 10 + '0');
    }
    int n, m;
    struct node{
        int l, r, qid, blo;
        int len(){
            return r - l + 1;
        }
        bool operator<(const node &rhs)const{
            if(blo ^ rhs.blo)return l < rhs.l;
            return blo & 1 ? r < rhs.r : rhs.r < r;
        }
    }query[limit];
    int cnt[limit],a[limit],sum[limit];
    int res;
    void add(int x){
        --sum[cnt[a[x]]];//减去多余部分
        ++cnt[a[x]];//增加一个count
        res = max(res, cnt[a[x]]);
        ++sum[cnt[a[x]]];
    }
    void del(int x){
        --sum[cnt[a[x]]];//撤回一个count
        if(res == cnt[a[x]] && !sum[cnt[a[x]]])--res;//如果没有了那就增加
        --cnt[a[x]];
        ++sum[cnt[a[x]]];
    }
    map<double, int>mp;
    int tot, vis[limit];
    int main(){
    #ifdef LOCAL
        FOPEN;
        //freopen("C:\\Users\\administrator01\\CLionProjects\\untitled24\\out.txt", "w", stdout);
    #endif
        n = read(), m = read(),
        tot = 0;
        rep(i ,1, n){
            double input;
            scanf("%lf" , &input);//扫一下
            if(!mp[input]){
                a[i] = mp[input] = ++tot;
            }else{
                a[i] = mp[input];
            }
        }
        int block = int(sqrt(n >= 3 ? n * (2.0 / 3) : n));//分块
        rep(i, 1, m){
            query[i].l = read(), query[i].r = read(), query[i].qid = i;
            query[i].blo = query[i].l / block;//分成块
        }
        sort(query + 1, query + 1 + m);
        int l = 0 , r = 0;
        res = 0;
        rep(i ,1, m){
            while(l < query[i].l)del(l++);//缩进
            while(l > query[i].l)add(--l);
            while(r < query[i].r)add(++r);
            while(r > query[i].r)del(r--);
            vis[query[i].qid] = res >= query[i].len() / 2 + 1;
        }
        rep(i ,1, m){
            puts(vis[i] ? "usable" : "unusable");
        }
        return 0;
    }
    
    展开全文
  • 我就记得开学的时候和谷老师说的那个区间众数查询的问题怎么似曾相识,原来是真的做过......

    题目链接: 洛谷 P4168 [Violet]蒲公英

    前言

    一遍过了,巨开心。记得高中的时候的代码,当时调试了三天才过。这次我才不在乎什么常数优化,写代码当然是越稳越好。

    Think twice, code once. —— WJMZBMR神犇

    #include <cstdio> /// 强制在线的区间众数 
    #include <algorithm>
    using namespace std;
    
    /// 由于这个题细节巨多,所以编程一定要严谨保命,步步思路都要非常清晰才行 
    
    const int maxn = 40000 + 5, maxsqrt = 200 + 5; /// 数据最大数量,最大块数目 
    
    namespace radix { /// 离散化工具 namespace 
    	int re[maxn]; /// 逆映射 
    	int tmp[maxn]; /// 临时数组 
    	
    	void solve(int* A, int n) { /// 将离散化数据存回 A,并记录离散化映射 
    		for(int i = 1; i <= n; i ++) tmp[i] = A[i];
    		sort(tmp + 1, tmp + n + 1);
    		for(int i = 1; i <= n; i ++) {
    			int val = A[i];
    			int nval = lower_bound(tmp + 1, tmp + n + 1, A[i]) - tmp; /// 值域是 1 ~ n 
    			A[i] = nval; re[nval] = val; /// A[i] 存入新值 
    		}
    	}
    	
    	void test(int n) { /// 用于检测离散化的正确性 
    		for(int i = 1; i <= n; i ++) printf("re[%3d] = %3d, ", i, re[i]);
    	}
    }
    
    namespace blocks { /// 分块大法 ( 这个地方极其容易写错,细节太多 ) 
    	const int BlockSize = 200; /// 块的大小为 200 
    
    	int* Norm; /// 原数列指针 
    	int N; /// 总元素个数 
    	
    	int BlockId[maxn]; /// 记录每个位置的 块 编号,末尾的值均为 0,最后不足一块的部分也算做一块 
    	int Pre[maxsqrt][maxn]; /// Pre[i][j] 表示前 i 块中 j 出现的次数 
    	int Seg[maxsqrt][maxsqrt]; /// Seg[i][j] 表示 第 i 块 到第 j 块的众数 
    	int Begin[maxsqrt]; /// 记录每个块的开始 
    	int End  [maxsqrt]; /// 记录每个块的结束位置 
    	int Bcnt = 0; /// 统计总块数 
    	
    	int tmp[maxn]; /// 万能数据桶:记得用后清空 ( 清空时务必考虑时间复杂度 ) 
    	
    	inline int ocur(int LB, int RB, int color) { /// 返回颜色 color 在第 blockId 块中出现的次数 
    		return Pre[RB][color] - Pre[LB - 1][color]; /// 差分 
    	}
    	inline int isEnd(int pos) { /// 判断某个位置是否是某个块的结尾 
    		return BlockId[pos] != BlockId[pos + 1] ? BlockId[pos] : 0; /// 不是结尾返回 0,否则返回块的编号 
    	}
    	
    	void init(int* norm, int n) { /// 初始化构造 
    		Norm = norm; N = n;
    		for(int i = 1; i <= n; i ++) {
    			BlockId[i] = (i-1)/BlockSize + 1; /// 块 编号从 1 开始向上增长 
    			End[BlockId[i]] = i; /// 覆盖法记录每个块的结束位置 
    			if(BlockId[i] != BlockId[i-1]) Begin[BlockId[i]] = i, Bcnt ++; /// 记录每个块的开始位置 
    		}
    		
    		/// 统计 Pre 数组 
    		for(int i = 1; i <= n; i ++) Pre[BlockId[i]][Norm[i]] ++; /// 先统计每个块内部的每种颜色出现的次数 
    		for(int j = 1; j <= n; j ++) /// 再对这 N 个长度为 Bcnt 的向量求前缀和 
    			for(int i = 2; i <= Bcnt; i ++) Pre[i][j] += Pre[i-1][j];
    			
    		/// 统计 Seg 数组 
    		for(int i = 1; i <= Bcnt; i ++) { /// 注意:此时 tmp 数据桶是空的 
    			int now = 0, cnt = 0;
    			for(int pos = Begin[i]; pos <= N; pos ++) {
    				int color = Norm[pos];
    				tmp[color] ++;
    				if((tmp[color] > cnt) || (tmp[color] == cnt && color < now)) { /// 时刻更新最小众数的值 
    					now = color;
    					cnt = tmp[color];
    				}
    				int id = isEnd(pos); /// 如果当前位置恰好是某个块的结尾 
    				if(id) Seg[i][id] = now; /// 当前的众数,就是第 i 块 到 第 id 块的区间众数 
    			}
    			/// 此时 tmp 数组中储存着 Begin[i] ~ N 的各种颜色的出现次数数据 
    			for(int pos = Begin[i]; pos <= N; pos ++) tmp[Norm[pos]] --; /// 利用回滚法清空数据桶 
    			/// 此时 tmp 数据桶是空的 
    		}
    	}
    	
    	int lastans = 0;
    	void regain(int& l, int& r) { /// 重新获得在线数据 
    		l = (l + lastans - 1) % N + 1;
    		r = (r + lastans - 1) % N + 1; /// lastans>=1 , 1<=l,r<=n
    		if(l > r) swap(l, r); /// 保证 l <= r 
    	}
    	
    	int exist[maxn]; /// 是否统计数据桶:exist[i] = 1 表示 已经统计了 颜色 i 的大区间信息 
    	
    	int solve(int Lpos, int Rpos) { /// 记得 re 离散化 
    		//printf("Lpos = %d, Rpos = %d\n", Lpos, Rpos);
    		int now = 0, cnt = 0;
    		if(BlockId[Rpos] - BlockId[Lpos] <= 1) { /// 区间非常的短,暴力统计众数,此时 tmp 数据桶为空 
    			for(int pos = Lpos; pos <= Rpos; pos ++) {
    				int color = Norm[pos]; /// 当前位置的颜色 
    				tmp[color] ++;
    				if((tmp[color] > cnt) || (tmp[color] == cnt && color < now)) { /// 更新当前的众数 
    					now = color;
    					cnt = tmp[color];
    				}
    			}
    			/// 现在 tmp 储存着 Lpos ~ Rpos 之间的数据桶信息 
    			for(int pos = Lpos; pos <= Rpos; pos ++) tmp[Norm[pos]] --; /// 利用回滚清空数据桶 
    		}else {
    			/// 我们只关注两侧零星的数据以及中间数据段的众数 
    			int LB = BlockId[Lpos] + 1;
    			int RB = BlockId[Rpos] - 1; /// 由于  BlockId[Rpos] - BlockId[Lpos] >= 2 所以 RB - LB >= 0
    			int mid = Seg[LB][RB]; /// 中间部分的众数 
    			
    			/// 注意: 现在 exist 数据桶是空的, tmp 数据桶也是空的 
    			exist[mid] = 1; tmp[mid] += ocur(LB, RB, mid);
    			now = mid; cnt = tmp[mid]; /// 初始值 
    			for(int i = Lpos; BlockId[i] == BlockId[Lpos]; i ++) { /// 统计左侧多余部分 
    				int color = Norm[i];
    				if(!exist[color]) exist[color] = 1, tmp[color] += ocur(LB, RB, color);
    				tmp[color] ++;
    				if((tmp[color] > cnt) || (tmp[color] == cnt && color < now)) { /// 更新当前的众数 
    					now = color;
    					cnt = tmp[color];
    				}
    			}
    			for(int i = Begin[BlockId[Rpos]]; i <= Rpos; i ++) { /// 统计右侧多余部分 
    				int color = Norm[i];
    				if(!exist[color]) exist[color] = 1, tmp[color] += ocur(LB, RB, color);
    				tmp[color] ++;
    				if((tmp[color] > cnt) || (tmp[color] == cnt && color < now)) { /// 更新当前的众数 
    					now = color;
    					cnt = tmp[color];
    				}
    			}
    			
    			/// 此时,一定要清空 tmp 数据桶和 exist 数据桶 
    			exist[mid] = 0; tmp[mid] = 0;
    			for(int i = Lpos; BlockId[i] == BlockId[Lpos]; i ++) exist[Norm[i]] = tmp[Norm[i]] = 0;
    			for(int i = Begin[BlockId[Rpos]]; i <= Rpos; i ++)   exist[Norm[i]] = tmp[Norm[i]] = 0;
    			/// 直接暴力清空 tmp 和 exist 就行 ( 回滚什么的是闲得无聊吧 ) 
    		}
    		return lastans = radix :: re[now];
    	}
    }
    
    int norm[maxn]; /// 储存离散化后的原数列 
    
    int main() {
    	int n, m; scanf("%d%d", &n, &m);
    	for(int i = 1; i <= n; i ++) scanf("%d", &norm[i]);
    	
    	radix :: solve(norm, n); /// 离散化 
    	//radix :: test(n);
    	
    	blocks :: init(norm, n); /// 初始化分块数据结构 
    	
    	for(int i = 1; i <= m; i ++) {
    		int l, r; scanf("%d%d", &l, &r);
    		blocks :: regain(l, r); /// 记得开 long long ( 手动  @NOI2018 归程 ) 
    		printf("%d\n", blocks :: solve(l, r));
    	}
    	return 0; 
    }
    
    展开全文
  • 区间众数

    2019-04-18 09:40:00
    大意: 区间询问众数出现次数, 强制在线. 先预处理出块间答案, 考虑每次询问左右边界, 显然最多使答案再增加$2\sqrt{n}$. 预处理时把相同元素按顺序存进vector里, 这样可以O(1)查询每个元素前后k次出现的位置, ...

    1. luogu P5048

    大意: 区间询问众数的出现次数, 强制在线.

     

    先预处理出块间答案, 考虑每次询问左右边界, 显然最多使答案再增加$2\sqrt{n}$. 预处理时把相同元素按顺序存进vector里, 这样可以O(1)查询每个元素前后k次出现的位置, 对于左边界若后ans次出现位置<=r, 则++ans, 右边界若前ans次出现位置>=l, 则++ans

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <set>
    #include <map>
    #include <queue>
    #include <string>
    #include <string.h>
    #include <bitset>
    #define REP(i,a,n) for(int i=a;i<=n;++i)
    #define PER(i,a,n) for(int i=n;i>=a;--i)
    #define hr putchar(10)
    #define pb push_back
    #define lc (o<<1)
    #define rc (lc|1)
    #define mid ((l+r)>>1)
    #define ls lc,l,mid
    #define rs rc,mid+1,r
    #define x first
    #define y second
    #define io std::ios::sync_with_stdio(false)
    #define endl '\n'
    #define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    const int P = 1e9+7, INF = 0x3f3f3f3f;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
    ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
    inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
    //head
    
    
    
    const int N = 5e5+10, M = 1000;
    int n, m, cnt, sz, ans;
    map<int,int> s;
    vector<int> val[N];
    int a[N], sum[N], blo[N], pos[N];
    int L[M], R[M], f[M][M];
    int id(int x) {
    	if (s.count(x)) return s[x];
    	int t = s.size();
    	return s[x]=t;
    }
    
    int main() {
    	scanf("%d%d", &n, &m);
    	REP(i,1,n) {
    		scanf("%d", a+i);
    		a[i] = id(a[i]);
    		val[a[i]].pb(i);
    		pos[i] = val[a[i]].size()-1;
    	}
    	sz = 710, cnt = (n-1)/sz+1;
    	REP(i,1,cnt) L[i]=R[i-1]+1,R[i]=i*sz;
    	R[cnt] = n;
    	REP(i,1,cnt) {
    		memset(sum,0,sizeof sum);
    		REP(j,L[i],R[i]) blo[j]=i;
    		REP(j,i,cnt) {
    			int &res = f[i][j] = f[i][j-1];
    			REP(k,L[j],R[j]) {
    				++sum[a[k]];
    				res = max(res, sum[a[k]]);
    			}
    		}
    	}
    	memset(sum,0,sizeof sum);
    	REP(i,1,m) {
    		int l, r;
    		scanf("%d%d", &l, &r);
    		l ^= ans, r ^= ans, ans = f[blo[l]+1][blo[r]-1];
    		if (blo[l]==blo[r]) {
    			REP(i,l,r) {
    				++sum[a[i]];
    				ans=max(ans,sum[a[i]]);
    			}
    			REP(i,l,r) sum[a[i]]=0;
    		}
    		else {
    			REP(i,l,R[blo[l]]) {
    				int res = pos[i], sz = val[a[i]].size();
    				while (res+ans<sz&&val[a[i]][res+ans]<=r) ++ans;
    			}
    			REP(i,L[blo[r]],r) {
    				int res = pos[i];
    				while (res-ans>=0&&val[a[i]][res-ans]>=l) ++ans;
    			}
    		}
    		printf("%d\n", ans);
    	}
    }

     

    2. luogu P4168

    大意: 区间询问最小众数, 强制在线.

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <set>
    #include <map>
    #include <queue>
    #include <string>
    #include <string.h>
    #include <bitset>
    #define REP(i,a,n) for(int i=a;i<=n;++i)
    #define PER(i,a,n) for(int i=n;i>=a;--i)
    #define hr putchar(10)
    #define pb push_back
    #define lc (o<<1)
    #define rc (lc|1)
    #define mid ((l+r)>>1)
    #define ls lc,l,mid
    #define rs rc,mid+1,r
    #define x first
    #define y second
    #define io std::ios::sync_with_stdio(false)
    #define endl '\n'
    #define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    const int P = 1e9+7, INF = 0x3f3f3f3f;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
    ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
    inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
    //head
    
    
    
    const int N = 5e5+10, M = 1000;
    int n, m, cnt, sz, ans;
    map<int,int> s;
    vector<int> val[N];
    int a[N], b[N], sum[N], blo[N], pos[N];
    int L[M], R[M], f[M][M], g[M][M];
    int id(int x) {
    	if (s.count(x)) return s[x];
    	int t = s.size()+1;
    	b[t] = x;
    	return s[x]=t;
    }
    
    int main() {
    	scanf("%d%d", &n, &m);
    	REP(i,1,n) {
    		scanf("%d", a+i);
    		a[i] = id(a[i]);
    		val[a[i]].pb(i);
    		pos[i] = val[a[i]].size()-1;
    	}
    	sz = 700, cnt = (n-1)/sz+1;
    	REP(i,1,cnt) L[i]=R[i-1]+1,R[i]=i*sz;
    	R[cnt] = n;
    	REP(i,1,cnt) {
    		memset(sum,0,sizeof sum);
    		REP(j,L[i],R[i]) blo[j]=i;
    		int ans = 0, mx = 0;
    		REP(j,i,cnt) {
    			REP(k,L[j],R[j]) {
    				++sum[a[k]];
    				if (sum[a[k]]>mx||sum[a[k]]==mx&&b[a[k]]<b[a[ans]]) ans=k,mx=sum[a[k]];
    			}
    			f[i][j] = ans, g[i][j] = mx;
    		}
    	}
    	memset(sum,0,sizeof sum);
    	REP(i,1,m) {
    		int l, r;
    		scanf("%d%d", &l, &r);
    		l = (l+ans-1)%n+1, r = (r+ans-1)%n+1;
    		if (l>r) swap(l,r);
    		ans = f[blo[l]+1][blo[r]-1];
    		int mx = g[blo[l]+1][blo[r]-1];
    		if (blo[l]==blo[r]) {
    			REP(i,l,r) {
    				++sum[a[i]];
    				if (sum[a[i]]>mx||sum[a[i]]==mx&&b[a[i]]<b[a[ans]]) ans=i,mx=sum[a[i]];
    			}
    			REP(i,l,r) sum[a[i]]=0;
    		}
    		else {
    			REP(i,l,R[blo[l]]) {
    				int res = pos[i], sz = val[a[i]].size(), p = res+mx;
    				if (0<=p-1&&p-1<sz&&val[a[i]][p-1]<=r) {
    					if (b[a[i]]<b[a[ans]]) ans=i;	
    				}
    				while (p<sz&&val[a[i]][p]<=r) ++p, ++mx, ans = i;
    			}
    			REP(i,L[blo[r]],r) {
    				int res = pos[i], sz = val[a[i]].size(), p = res-mx;
    				if (0<=p+1&&p+1<sz&&val[a[i]][p+1]>=l) {
    					if (b[a[i]]<b[a[ans]]) ans=i;
    				}
    				while (p>=0&&val[a[i]][p]>=l) --p, ++mx, ans = i;
    			}
    		}
    		printf("%d\n", ans=b[a[ans]]);
    	}
    }
    

     

    转载于:https://www.cnblogs.com/uid001/p/10727709.html

    展开全文
  • 区间众数(分块思想) ...题目大意:给一个数组,q次在线查询,每次查询L-R中出现次数最多且最小的数。 解题思路: 首先我们把这个数组分为k块来看待,然而每次查询的L-R则有几种可能,如下图 ...

    区间众数(分块思想)

    题目链接:蒲公英

    拓展题:作诗

    题目大意:给一个数组,q次在线查询,每次查询L-R中出现次数最多且最小的数。

    解题思路:
    	首先我们把这个数组分为k块来看待,然而每次查询的L-R则有几种可能,如下图
    

    在这里插入图片描述

    	1、对于第一种情况,当L与R属于同一个区间时,我们只需要暴力计算即可
    
    	2、对于第二种情况,我们需要把L到L所在的块的右边界的数统计,再把R所在的块的左边界到R的数统计即可
    	
    	3、对于三种情况,我们预处理出所以数在任意两块中出现的次数,
    	然后再暴力计算L到L所在的块的右边界的数再把R所在的块的左边界到R的数,相加即可。
    

    过程中会使用到前缀和思想,即求一个数在任意两个区间出现的次数表示为sum[y][j]-sum[x-1][j],意思是第x块到第y块区间j出现的次数

    sum[i][j]:表示为从开始到第i块位置,j出现的次数
    cnti[i]:表示为i出现的次数
    MIN[i][j]:表示为第i块到第j块出现次数最多且最小的数

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=4e4+7,M=207;
    int a[N],A[N],Len,n,q;//a表示存放数组,A表示a的离散化,Len表示离散化后数组长度
    int B[N],BL;//B[i]表示i下标属于哪一块,BL表示块的长度
    int sum[M][N],MIN[M][M],cnt[N];
    //sum[i][j]表示从开始到第i块j出现的次数,MIN[i][j]表示第i块到第j块出现次数最多且最小的数,cnt[i]表示i出现的次数
    void Build(){
        for(int i=1;i<=B[n];i++){//枚举每一块,B[n]表示n所在的块,也就是块的总数
            for(int j=1;j<=Len;j++)sum[i][j]=sum[i-1][j];//当前i块的j出现的次数,肯定包括i-1块j出现的次数
            for(int j=(i-1)*BL+1;j<=n&&j<=i*BL;j++)sum[i][a[j]]++;//再从i块的最左侧开始枚举j
        }
    
        for(int i=1;i<=B[n];i++){//枚举每一块
            int ans=0,res=0;//ans记录当前出现次数最多且最小的数,res记录当前出现最多的次数
            for(int j=(i-1)*BL+1;j<=n;j++){//从当前i块到最后为止
                cnt[a[j]]++;//a[j]出现的次数
                if(cnt[a[j]]>res||cnt[a[j]]==res&&A[a[j]]<A[ans]){//如果出现的次数大于之前或者次数相等于之前,当数小于之前就更新
                    res=cnt[a[j]];
                    ans=a[j];
                }
                MIN[i][B[j]]=ans;//当前i块到j所在的块的当前答案
            }
            memset(cnt,0,sizeof cnt);
        }
    }
    
    int query(int L,int R){
        int x=B[L],y=B[R],ans=MIN[x+1][y-1],res=max(0,sum[y-1][ans]-sum[x][ans]),lim=min(x*BL,R),f=0;
        //x表示L所在的块,y表示R所在的块,ans表示L-R中间的块的出现次数最多且最小的数(不包括L、r所在的块),如果L与R中间没有块,则为0。
        //res表示L-R中间的块的出现最多的数的次数(不包括L、r所在的块),这里利用前缀和思想,如果L与R中间没有块,则为0。
        //lim表示L所在的块的边界(如果R与L在同一块则到R中止),f表示L、R是否在同一块。
    
        if(x!=y)f=1;
        for(int i=L;i<=lim;i++){
            cnt[a[i]]=max(0,sum[y-1][a[i]]-sum[x][a[i]]);//前缀和求L所在的块出现的数,在L-R中出现的次数(不包括L、r所在的块)
        }
        if(f){
            for(int i=(y-1)*BL+1;i<=R;i++){
                cnt[a[i]]=max(0,sum[y-1][a[i]]-sum[x][a[i]]);//前缀和求R所在的块出现的数,在L-R中出现的次数(不包括L、r所在的块)
            }
        }
        for(int i=L;i<=lim;i++){//暴力枚举L所在的块
            cnt[a[i]]++;
            if(cnt[a[i]]>res||cnt[a[i]]==res&&A[a[i]]<A[ans]){//如果满足条件就更新答案
                res=cnt[a[i]];
                ans=a[i];
            }
        }
        if(f){
            for(int i=(y-1)*BL+1;i<=R;i++){//暴力枚举R所在的块
                cnt[a[i]]++;
                if(cnt[a[i]]>res||cnt[a[i]]==res&&A[a[i]]<A[ans]){//如果满足条件就更新答案
                    res=cnt[a[i]];
                    ans=a[i];
                }
            }
        }
        return ans;//返回的答案是离散化后的结果
    }
    int main(){
        cin>>n>>q;BL=sqrt(n);//块的长度
        for(int i=1;i<=n;i++){
            cin>>a[i];
            A[i]=a[i];
            B[i]=(i-1)/BL+1;//当前i下标属于哪一块
        }
        //离散化处理
        sort(A+1,A+1+n);
        Len=unique(A+1,A+1+n)-A-1;
        for(int i=1;i<=n;i++)a[i]=lower_bound(A+1,A+1+Len,a[i])-A;
        
        Build();//建块预处理
        
        int x=0,L,R;//题目输入要求,在线处理
        while(q--){
            cin>>L>>R;
            L=(L+x-1)%n+1,R=(R+x-1)%n+1;
            if(L>R)swap(L,R);
            x=A[query(L,R)];//query返回的是离散化后的下标
            cout<<x<<endl;
        }
    	return 0;
    }
    
    展开全文
  • 两种做法都是要用到分块 在线的题的地址是... 题意简化就是求一个区间内的最大众数,本来是看了网上的在线区间众数求法(https://blog.csdn.net/BerryKanry/article/details/75478987?location...
  • luogu4168蒲公英(区间众数) 给定n个数,m个区间询问,问每个询问中的众数是什么。 题面很漂亮,大家可以去看一下。 对于区间众数,由于区间的答案不能由子区间简单的找出来,所以似乎不能用树形结构。 用分块的...
  • 题解: 把分块9求区间众数那题代码稍稍改了改就ok了,pair被迫换成俩int,要不老有错、、、 3.ac代码: #include #include using namespace std; typedef long long ll; const int N = 1e6 + 10; int f[5003][5003];...
  • 查询区间众数,要求强制在线 设有T个块 1.众数只可能在大块[L,R]里或者两端[l,L) (R,r]里出现 2.大块的众数只要预处理打表一下即可,复杂度n*T(这样的区间有T*T个) 3.两端的众数需要枚举每个元素,然后查询这...
  • 查询的时候想办法找区间出现最多的数,主席树的查询,恰好可以,求到出现次数,但是如何找到出现次数又成了新的问题,加之还要求最小的众数,又构成了新的问题 最早的想法是二分,但是后来发现问题不具有单调性...
  • 区间众数(分块)

    2021-07-18 12:15:48
    n个数构成一个序列,查询 [L,R][L, R][L,R] 区间出现次数最多的那个数的出现次数。时间、空间复杂度要求均为:O(n⋅n)O(n\cdot \sqrt{n})O(n⋅n​)。 分析 基本思想:分块 离散化,使得序列元素ana_nan​ 转换成 ...
  • 【分块】区间众数

    2016-11-17 19:58:00
    总共有n个数,m个询问,对于每个询问[l,r]求出区间众数出现次数 1<=n<=10000,1<=m<=20000 【做法】 我当时还不会莫队只能用分块来做......结果学长说这是莫队模板题比较尴尬 首先先离散化处理...
  • [ZJb417]区间众数

    2018-02-06 17:44:00
    题目大意:  给定一个长度为$n(1\leq n\leq10^5)$的正整数序列$s(1\leq s_i\leq n)$,对于$m(1\leq m\leq10^)$次询问$l,r$,每次求区间$[s_l,\ldots,s_r]$中,众数出现次数以及众数的个数。 思路:  莫队。  ...
  • 树分块 区间众数
  • 在线区间众数的分块做法比较多,这里提供一个思路: 首先离散化一下比较方便。 可以推导出:[L, R]的众数一定是整数块的众数,或者两个边块的数。 所以对于每次查询,众数的可能值最多有2sqrt(n)+1个 所以我们可以...
  • 蒲公英 Description 在乡下的小路旁种着许多蒲公英,而我们的问题正是与...而每次询问一个区间[l,r],你需要回答区间出现次数最多的是哪种蒲公英,如果有若干种蒲公英出现次数相同,则输出种类编号最小的那个。...
  • 给出一个长度为 nnn 的序列,有 mmm 次询问,每次询问给出 [l,r][l,r][l,r],求区间众数。强制在线。 n,m≤500000n,m\leq 500000n,m≤500000。 分析 首先对 aia_iai​ 离散化,现在值域变成了 [1,n][1,n][1,n]。 ...
  • 区间的离线查询首先想到莫队,看到题目的限制就会想到我们需要求得区间众数。我们用cnt[]数组记录每个数出现次数,在进行莫队add操作时:众数的维护很简单,只要与加入的数出现次数取大即可;在进行莫队del...
  • 做题笔记,CF 4.19Div2 D CF1514D Cut and Stick(区间众数:线段树 or 莫队) 题目大意 给你一个长度为n的序列和q个询问。(n,q<=3e5)(n,q<=3e5)(n,q<=3e5) 每次询问一个区间(l,r)(l,r)(l,...2.假如区间众数出现
  • 「科技」区间众数

    2019-05-13 12:53:00
    莫队呀,由于众数不好删除,直接回滚莫队即可,时间复杂度\(o(n \sqrt n)\),空间$o(n) $。 在线 分块啊。 设块大小为T。 first 其实可以沿用回滚莫队思想,记录\([l,r]\)块里的数的\(cnt\),时间复杂度\(\...
  • bzoj 2724: [Violet 6]蒲公英 区间众数 分块
  • Input Output Sample Input 6 3 1 2 3 2 1 2 1 5 3 6 1 5 Sample Output ...求区间众数 题解: 见代码 //解决本题的重要性质: //对于两个区间a,b,其中已知a区间的众数k //则众数一定为k或是b区间...
  • 题面: Description Input ...l = (l_0 + x – 1) mod n + 1, r = (r_0 + x – 1) mod n + 1 ...在线区间众数的分块做法比较多,这里提供一个思路: 首先离散化。显然某个区间内的众数应该是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,520
精华内容 1,008
关键字:

查询区间众数出现次数