网站开发结语,怎么联系网站开发团队,怎么才可以做网站,株洲网站排名题目
题目链接
题意
修改#xff1a;将一个区间内所有的数C。查询#xff1a;查询一个区间内C的数字有多少个。
题解
很经典的分快算法题目。 将数列分块以后#xff0c;对块内的元素进行排序。
当我们要做修改操作的时候#xff1a;遇到要修改的完整的块的时候…题目
题目链接
题意
修改将一个区间内所有的数C。查询查询一个区间内C的数字有多少个。
题解
很经典的分快算法题目。 将数列分块以后对块内的元素进行排序。
当我们要做修改操作的时候遇到要修改的完整的块的时候我们给它在addmark数组的相应的位置C标记为我对整个区间做了一个修改操作有点类似于带lazy标记的线段树的操作。当要修改的部分区间不是完整的块的时候我们检查这部分区间所在的块的addmark有没有被标记如果有就对这个块整个进行更新操作然后把addmark清零并且暴力把这部分区间的元素C。时间复杂度为O(n‾√n‾√∗logn‾√))O(nn∗logn))O(\sqrt{n} + \sqrt{n}*log\sqrt{n}))。当我们遇到查询操作的时候当我们要查询的部分区间不属于完整的块的时候如果块的addmark被标记过了那么更新这个块然后再暴力查询这个“部分区间”。当我们要查询的区间属于完整的块的时候由于这个区间是有序的我们只需要使用二分搜索结合addmark就可以确定出该块内C的元素有多少个。时间复杂度O(n‾√n‾√∗logn‾√))O(nn∗logn))O(\sqrt{n} + \sqrt{n}*log\sqrt{n}))。
因此总的时间复杂度就是:O((n‾√n‾√∗logn‾√)∗m)O((nn∗logn)∗m)O((\sqrt{n} + \sqrt{n}*log\sqrt{n})*m)
代码
#include iostream
#include algorithm
#include cstdio
#include vector
using namespace std;
typedef long long ll;
#define pr(x) cout#x:xendl
int Base 1000;
ll a[1000007],addmark[1007],C;
int n,q,L,R;
char op;
vectorll vec[1007];inline void read(ll x){scanf(%lld,x);
}inline void read(int x){scanf(%d,x);
}inline void read(char c){scanf( %c,c);
}void work(int bl){if(addmark[bl]){for(int t bl*Base;t (bl1)*Base t n;t){a[t] addmark[bl];}for(auto i : vec[bl]){i addmark[bl];}addmark[bl] 0;}
}void buildvec(int bl){vec[bl].clear();for(int t bl*Base;t (bl1)*Base t n;t){vec[bl].push_back(a[t]);}sort(vec[bl].begin(),vec[bl].end());
}int main(){scanf(%d%d,n,q);for(int i 0;i n;i){int bl i/Base;read(a[i]);vec[bl].push_back(a[i]);if((i1)%Base 0 || i n-1){sort(vec[bl].begin(),vec[bl].end());}}for(int i 0;i q;i){read(op);read(L);read(R);read(C);L--;R--;ll rep 0;if(op A){if(L % Base ! 0 addmark[L/Base]) {work(L / Base);}if((R1)%Base ! 0 addmark[R/Base]){work(R / Base);}int ans 0;for(;L R L % Base ! 0;L){ans a[L] C;}for(;L R (R1)%Base ! 0;R--){ans a[R] C;}if(L R){printf(%d\n,ans);continue;}int bl L / Base;int br R / Base;for(;bl br;bl){auto loc lower_bound(vec[bl].begin(),vec[bl].end(),C-addmark[bl]);int ad vec[bl].size() - (loc - vec[bl].begin());ans max(0,ad);}printf(%d\n,ans);}else{int bl,br;if(L % Base ! 0){work(L / Base);bl L / Base;for(;L R L % Base ! 0;L){a[L] C;//pr(L);//pr(a[L]);}buildvec(bl);}if((R1) % Base ! 0){work(R / Base);br R / Base;for(;L R (R1) % Base ! 0;--R)a[R] C;buildvec(br);}if(L R){bl L / Base;br R / Base;for(;bl br;bl){addmark[bl] C;}}}}return 0;
}
