做几个小网站还是做一个大网站,网站办事服务建设情况,重庆造价信息网官网首页,发号网站源码传送门 这道题序列很长#xff0c;但是操作数很少#xff0c;然后也没想到什么好的数据结构来维护#xff0c;那就分块吧。 感觉维护的过程很好想#xff0c;修改的时候对于整个块都在内的直接打标记#xff0c;两个零散的区间暴力重构#xff0c;重新排序。查询的时候但是操作数很少然后也没想到什么好的数据结构来维护那就分块吧。 感觉维护的过程很好想修改的时候对于整个块都在内的直接打标记两个零散的区间暴力重构重新排序。查询的时候对于整块的直接在块内lowerbound一下z-add[i]的位置零散的话直接暴力计算即可。 复杂度Oksqrt(n)logsqrt(n).注意数组别开小了…… #includecstdio
#includealgorithm
#includecstring
#includeiostream
#includecmath
#includeset
#includequeue
#define rep(i,a,n) for(int i a;i n;i)
#define per(i,n,a) for(int i n;i a;i--)
#define enter putchar(\n)using namespace std;
typedef long long ll;
const int M 2000005;
const int N 2005;
const ll INF 1e179;
const ll mod 19260817;ll read()
{ll ans 0,op 1;char ch getchar();while(ch 0 || ch 9){if(ch -) op -1;ch getchar();}while(ch 0 ch 9){ans * 10;ans ch - 0;ans % mod;ch getchar();}return ans * op;
}ll a[M],b[N][N],l[N],r[N],blo[M],add[N],n,m,B,cnt,g 1,x,y,z;
char s[5];ll query(ll x,ll y,ll z)
{ll L blo[x],R blo[y],ans 0;if(L R){rep(i,x,y) if(a[i] add[L] z) ans;return ans;}rep(i,L1,R-1){//rep(j,1,B) printf(%lld ,b[i][j]);enter;//printf(!%lld\n,z - add[i]);int d lower_bound(b[i]1,b[i]B,z - add[i]) - b[i];//printf(#%d\n,d);if(d B b[i][d] z - add[i]) continue;ans B - d 1;}rep(i,x,r[L]) if(a[i] add[blo[i]] z) ans;rep(i,l[R],y) if(a[i] add[blo[i]] z) ans;return ans;
}void modify(ll x,ll y,ll z)
{ll L blo[x],R blo[y],cur 0;if(L R){rep(i,x,y) a[i] z;rep(i,l[L],r[L]) b[L][cur] a[i];sort(b[L]1,b[L]1B);return;}rep(i,L1,R-1) add[i] z;rep(i,x,r[L]) a[i] z;rep(i,l[R],y) a[i] z;rep(i,l[L],r[L]) b[L][cur] a[i];sort(b[L]1,b[L]B1),cur 0;rep(i,l[R],r[R]) b[R][cur] a[i];sort(b[R]1,b[R]B1);
}int main()
{n read(),m read(),B sqrt(n);cnt (n % B) ? n / B 1 : n / B;rep(i,1,cnt) l[i] r[i-1] 1,r[i] l[i] B - 1;r[cnt] n;rep(i,1,n) a[i] read();rep(i,1,n){blo[i] g;if(i r[g]) g;}rep(i,1,cnt){int cur 0;rep(j,l[i],r[i]) b[i][cur] a[j];sort(b[i]1,b[i]B1);}rep(i,1,m){scanf(%s,s);x read(),y read(),z read();if(s[0] A) printf(%lld\n,query(x,y,z));else modify(x,y,z);}return 0;
} 转载于:https://www.cnblogs.com/captain1/p/9834471.html
