首页 > 代码库 > Gym 100960G （set+树状数组）
Gym 100960G （set+树状数组）
Problem Youngling Tournament
题目大意
给一个序列a[i]，每次操作可以更改一个数，每次询问 将序列排序后有多少个数a[i]>=sum[i-1]。
n<=10^5,q<=5*10^4，a[i]<=10^12
解题分析
可以发现，在最优情况下，该序列长度最多为logn。
将询问离线后，用multiset来维护a[i],用树状数组来维护sum[i]。树状数组所存下标为离散化后的a[i]。
每次查询时跳跃式地在set中查找。
时间复杂度 O((n+m)log(n+m)+mlognlogn)
参考程序
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define N 100008 19 #define M 50008 20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define bitcnt(x) __builtin_popcount(x) 25 #define rep(x,y,z) for (int x=y;x<=z;x++) 26 #define repd(x,y,z) for (int x=y;x>=z;x--) 27 const int mo = 1000000007; 28 const int inf = 0x3f3f3f3f; 29 const int INF = 2000000000; 30 /**************************************************************************/ 31 32 int n,m,tot,flag; 33 LL a[N],c[N],x[N*2]; 34 int b[N]; 35 multiset<long long> S; 36 struct Binary_Indexed_Tree{ 37 LL a[N*3]; 38 void clear(){ 39 clr(a,0); 40 } 41 void insert(int x,LL val){ 42 for (int i=x;i<=N<<1;i+=i & (-i)) 43 a[i]+=val; 44 } 45 LL sigma(int x){ 46 LL res=0; 47 for (int i=x;i>0;i-=i & (-i)) 48 res+=a[i]; 49 return res; 50 } 51 LL query(int x,int y){ 52 return sigma(y)-sigma(x-1); 53 } 54 }T; 55 int id(LL xy){ 56 return lower_bound(x+1,x+tot+1,xy)-x; 57 } 58 set <long long> :: iterator it,it1; 59 void query(){ 60 int ans=1; LL tmp; 61 it = S.begin(); 62 it1 = it ; it1++; 63 if (*it==*it1) ans++; 64 tmp=T.sigma(id(*it)); 65 while (1){ 66 it = S.lower_bound(tmp); 67 if (it==S.begin()) it++; 68 if (it==S.end()) break; 69 it1 = it; it1--; 70 tmp=T.sigma(id(*it1)); 71 if (*it>=tmp) ans++; 72 tmp=T.sigma(id(*it)); 73 } 74 printf("%d\n",ans); 75 76 } 77 78 int main(){ 79 scanf("%d",&n); 80 rep(i,1,n){ 81 scanf("%lld",&a[i]); 82 x[++tot]=a[i]; 83 } 84 scanf("%d",&m); 85 rep(i,1,m){ 86 scanf("%d%lld",&b[i],&c[i]); 87 x[++tot]=c[i]; 88 } 89 sort(x+1,x+tot+1); 90 tot=unique(x+1,x+tot+1)-x; 91 T.clear(); 92 rep(i,1,n){ 93 T.insert(id(a[i]),a[i]); 94 S.insert(a[i]); 95 } 96 query(); 97 rep(i,1,m){ 98 S.erase(S.find(a[b[i]])); 99 T.insert(id(a[b[i]]),-a[b[i]]);100 S.insert(c[i]);101 T.insert(id(c[i]),c[i]);102 a[b[i]]=c[i];103 query();104 }105 106 }
Gym 100960G （set+树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。