Codeforces 220B - Little Elephant and Array 离线树状数组

2024-05-28 04:48

本文主要是介绍Codeforces 220B - Little Elephant and Array 离线树状数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!



This problem can be solve in simpler O(NsqrtN) solution, but I will describe O(NlogN) one.

We will solve this problem in offline. For each x (0 ≤ x < n) we should keep all the queries that end in x. Iterate that x from 0 to n - 1. Also we need to keep some array D such that for current x Dl + Dl + 1 + ... + Dx will be the answer for query [l;x]. To keep D correct, before the processing all queries that end in x, we need to update D. Let t be the current integer in A, i. e. Ax, and vector P be the list of indices of previous occurences of t (0-based numeration of vector). Then, if |P| ≥ t, you need to add 1 to DP[|P| - t], because this position is now the first (from right) that contains exactly t occurences of t. After that, if |P| > t, you need to subtract 2 from DP[|P| - t - 1], in order to close current interval and cancel previous. Finally, if |P| > t + 1, then you need additionally add 1 to DP[|P| - t - 2] to cancel previous close of the interval.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)const int MAXN = 1e5+100;
int n,m;int a[MAXN],c[MAXN],ans[MAXN];
struct Query
{int l,r,id;bool operator < (const Query &t) const {return r<t.r;}
}q[MAXN];
inline int lowbit(int x){return x&(-x);}
void add(int i, int v)
{while(i<=n){c[i]+=v;i+=lowbit(i);}
}
int sum(int x)
{int ret=0;while(x>0){ret+=c[x];x-=lowbit(x);}return ret;
}int main()
{int sz;while(~scanf("%d%d",&n,&m)){vector<int>data[MAXN];CL(c,0);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+1+m);for(int i=1,k=1;i<=n;i++){if(a[i]<=n){data[a[i]].push_back(i);sz=data[a[i]].size();if(sz>=a[i]){add(data[a[i]][sz-a[i]],1);if(sz>a[i])add(data[a[i]][sz-a[i]-1],-2);if(sz>a[i]+1)add(data[a[i]][sz-a[i]-2],1);}}while(q[k].r==i && k<=m){ans[q[k].id]=sum(q[k].r)-sum(q[k].l-1);k++;}}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0;
}

用于调试理解的及及加了注释的代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)const int MAXN = 1e5+100;
int n,m;int a[MAXN],c[MAXN],ans[MAXN];
struct Query
{int l,r,id;bool operator < (const Query &t) const {return r<t.r;}
}q[MAXN];
inline int lowbit(int x){return x&(-x);}
void add(int i, int v)
{while(i<=n){c[i]+=v;i+=lowbit(i);}
}
int sum(int x)
{int ret=0;while(x>0){ret+=c[x];x-=lowbit(x);}return ret;
}int main()
{int sz;while(~scanf("%d%d",&n,&m)){vector<int>data[MAXN];CL(c,0);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+1+m);for(int i=1,k=1;i<=n;i++){if(a[i]<=n){data[a[i]].push_back(i);sz=data[a[i]].size();if(sz>=a[i]){add(data[a[i]][sz-a[i]],1);//从右往左第a[i]次出现a[i]的位置+1if(sz>a[i])add(data[a[i]][sz-a[i]-1],-2);//从右往左第a[i]+1次出现a[i]的位置 -2,//因为当Sz==a[i]的时候,这个位置已经被加过1,此次读到i的时候,//从右往左第a[i]次出现a[i]的位置也被+1,//那么查询第a[i]+1次出现a[i]的位置到i,答案就是-2+1+1=0,//查询第a[i]次出现a[i]的位置到i,答案就是1if(sz>a[i]+1)add(data[a[i]][sz-a[i]-2],1);//从右往左第a[i]+2次出现a[i]的位置 +1,之前被+1-2,所以变成0//这三行代码维护出来,从当前的i往左数,第a[i]次出现a[i]的位置总是1//第a[i]+1次出现a[i]的位置总是-1,第a[i]+2及更多次的位置总是0,这样以i为右端点的区间的查询结果就都对了}}while(q[k].r==i && k<=m){/printf("#i=%d#\n",i);for(int j=0;j<=n;j++)printf("c[%d]=%d\n",j,c[j]);//ans[q[k].id]=sum(q[k].r)-sum(q[k].l-1);k++;}}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0;
}


这篇关于Codeforces 220B - Little Elephant and Array 离线树状数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1009580

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou