建筑公司名称大全简单大气两个字,重庆seo博客,惠州网站排名提升,中学校园网网站建设规划书传送门 这道题序列很长#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
