Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //A
- #include <bits/stdc++.h>
- using namespace std;
- struct Note{
- int l;
- int r;
- int ans;
- int d=0;
- };
- void build(vector<Note>& tree, vector<int>& a, int L, int R, int i){
- tree[i].l=L;
- tree[i].r=R;
- if (R-L==1){
- tree[i].ans=a[L];
- return;
- }
- int M=(R+L)/2;
- build(tree, a, L, M, 2*i+1);
- build(tree, a, M, R, 2*i+2);
- tree[i].ans=max(tree[2*i+1].ans, tree[2*i+2].ans);
- }
- void push(vector<Note>& tree, int i){
- tree[2*i+1].d+=tree[i].d;
- tree[2*i+2].d+=tree[i].d;
- tree[i].d=0;
- }
- void change(vector<Note>& tree, int i, int x, int L, int R){
- if (tree[i].l>=R || tree[i].r<=L){
- return;
- }
- if(tree[i].l>=L && tree[i].r<=R){
- tree[i].d+=x;
- return;
- }
- push(tree, i);
- change(tree, 2*i+1, x, L, R);
- change(tree, 2*i+2, x, L, R);
- tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
- }
- int answer(vector<Note>& tree, int i, int L, int R){
- if (tree[i].l>=R || tree[i].r<=L){
- return -1;
- }
- if(tree[i].l>=L && tree[i].r<=R){
- return tree[i].ans+tree[i].d;
- }
- push(tree, i);
- int m1=answer(tree, 2*i+1, L, R);
- int m2=answer(tree, 2*i+2, L, R);
- tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
- return max(m1, m2);
- }
- int main(){
- int n;
- cin>>n;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- cin>>a[i];
- }
- vector<Note> tree(4*n);
- build(tree, a, 0, n, 0);
- int M;
- cin>>M;
- for (int i=0; i<M; i++){
- char x;
- cin>>x;
- if (x=='a'){
- int L, R, add;
- cin>>L>>R>>add;
- L--;
- change(tree, 0, add, L, R);
- }else{
- int L, R;
- cin>>L>>R;
- L--;
- cout<<answer(tree, 0, L, R)<<" ";
- }
- }
- return 0;
- }
- //B
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- struct Note{
- int pref;
- int suf;
- int ans;
- };
- void build(vector<Note>& tree, vector<int>& a, int v, int l, int r){
- if (r-l==1){
- if (a[l]==0){
- tree[v].pref=1;
- tree[v].suf=1;
- tree[v].ans=1;
- }else{
- tree[v].pref=0;
- tree[v].suf=0;
- tree[v].ans=0;
- }
- return;
- }
- int m=(l+r)/2;
- build(tree, a, 2*v+1, l, m);
- build(tree, a, 2*v+2, m, r);
- tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
- tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
- tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
- if (tree[2*v+2].ans==r-m){
- tree[v].suf=tree[2*v+1].suf+r-m;
- }else{
- tree[v].suf=tree[2*v+2].suf;
- }
- if (tree[2*v+1].ans==m-l) {
- tree[v].pref = m - l + tree[2 * v + 2].pref;
- }else{
- tree[v].pref=tree[2*v+1].pref;
- }
- }
- void change(vector<Note>& tree, vector<int>& a, int v, int l, int r, int pos, int x){
- if (r-l==1){
- if (x==0){
- tree[v].pref=1;
- tree[v].suf=1;
- tree[v].ans=1;
- }else{
- tree[v].pref=0;
- tree[v].suf=0;
- tree[v].ans=0;
- }
- return;
- }
- int m=(r+l)/2;
- if (pos<m){
- change(tree, a, 2*v+1, l, m, pos, x);
- }else{
- change(tree, a, 2*v+2, m,r, pos, x);
- }
- tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
- tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
- tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
- if (tree[2*v+2].ans==r-m){
- tree[v].suf=tree[2*v+1].suf+r-m;
- }else{
- tree[v].suf=tree[2*v+2].suf;
- }
- if (tree[2*v+1].ans==m-l) {
- tree[v].pref = m - l + tree[2 * v + 2].pref;
- }else{
- tree[v].pref=tree[2*v+1].pref;
- }
- }
- int ans(vector<Note>& tree, vector<int>& a, int v, int l, int r, int L, int R){
- if (L>=r || R<=l){
- return 0;
- }
- if (L<=l && R>=r){
- //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<tree[v].ans<<"\n";
- return tree[v].ans;
- }
- int m=(r+l)/2;
- if (L<=m && R<=m){
- return ans(tree, a, 2*v+1, l, m, L, R);
- }
- if (L>=m && R>=m){
- return ans(tree, a, 2*v+2, m, r, L, R);
- }
- //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref)<<"\n";
- int y=min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref);
- y=max(y, ans(tree, a, 2*v+1, l, m, L, R));
- y=max(y, ans(tree, a, 2*v+2, m, r, L, R));
- return y;
- }
- signed main(){
- int N;
- cin>>N;
- if (N<10000){
- vector<int> q(N);
- for (int i=0; i<N; i++){
- cin>>q[i];
- }
- int m;
- cin>>m;
- while(m--){
- char type;
- cin>>type;
- if (type=='+'){
- int L, R, d;
- cin>>L>>R>>d;
- L--;
- for (int i=L; i<R; i++){
- q[i]+=d;
- }
- }else{
- int L, R;
- cin>>L>>R;
- L--;
- int ans=0;
- int cnt=0;
- for (int i=L; i<R-1; i++){
- if (q[i+1]-q[i]!=1){
- cnt=0;
- }else{
- cnt++;
- }
- ans=max(ans, cnt);
- }
- cout<<ans+1<<"\n";
- }
- }
- return 0;
- }
- vector<int> b(N);
- for (int i=0; i<N; i++) {
- cin>>b[i];
- }
- int n=N-1;
- vector<int> a(n);
- for (int i=0; i<n; i++){
- a[i]=b[i+1]-b[i]-1;
- }
- vector<Note> tree(4*n);
- build(tree, a, 0, 0, n);
- int m;
- cin>>m;
- while(m--){
- char type;
- cin>>type;
- if (type=='+'){
- int L, R, d;
- cin>>L>>R>>d;
- L--;
- if (L-1>=0 && L-1<n){
- a[L-1]+=d;
- change(tree, a, 0, 0, n, L-1, a[L-1]);
- }
- if (R-1<n && R-1>=0){
- a[R-1]-=d;
- change(tree, a, 0, 0, n, R-1, a[R-1]);
- }
- }
- else{
- int L, R;
- cin>>L>>R;
- L--;
- if (L==n || L==R-1){
- cout<<1<<"\n";
- continue;
- }
- cout<<ans(tree, a, 0, 0, n, L, R-1)+1<<"\n";
- }
- }
- return 0;
- }
- //C
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- struct Note{
- vector<int> v;
- int l;
- int r;
- int d=0;
- };
- vector<int> binary_rep(int x){
- vector<int> ans;
- while(x>0){
- ans.push_back(x%2);
- x/=2;
- }
- while(ans.size()<40){
- ans.push_back(0);
- }
- reverse(ans.begin(), ans.end());
- return ans;
- }
- void unite(vector<int>& vert, vector<int>& left, vector<int>& right){
- for (int i=0; i<40; i++){
- vert[i]=left[i]+right[i];
- }
- }
- void build(vector<Note>& tree, int idx, int L, int R, vector<vector<int>>& a){
- (tree[idx].v).resize(40);
- tree[idx].l=L;
- tree[idx].r=R;
- if (R-L==1){
- tree[idx].v=a[L];
- return;
- }
- int M=(L+R)/2;
- build(tree, 2*idx+1, L, M, a);
- build(tree, 2*idx+2, M, R, a);
- unite(tree[idx].v, tree[2*idx+1].v, tree[2*idx+2].v);
- }
- void push(vector<Note>& tree, int idx){
- tree[2*idx+1].d=tree[idx].d^tree[2*idx+1].d;
- tree[2*idx+2].d=tree[idx].d^tree[2*idx+2].d;
- tree[idx].d=0;
- }
- vector<int> counting_vector(vector<int>& ans, int x, int k){
- vector<int> cnt(40);
- for (int i=0; i<40; i++){
- if (!((x>>(39-i))&1)){
- cnt[i]=ans[i];
- }else{
- cnt[i]=k-ans[i];
- }
- }
- return cnt;
- }
- void change(vector<Note>& tree, int idx, int L, int R, int x){
- if (tree[idx].l>=R || tree[idx].r<=L){
- return;
- }
- if (L<=tree[idx].l && R>=tree[idx].r){
- tree[idx].d=tree[idx].d^x;
- return;
- }
- push(tree, idx);
- change(tree, 2*idx+1, L, R, x);
- change(tree, 2*idx+2, L, R, x);
- int len1=tree[2*idx+1].r-tree[2*idx+1].l;
- int len2=tree[2*idx+2].r-tree[2*idx+2].l;
- vector<int> y1=counting_vector(tree[2*idx+1].v, tree[2*idx+1].d, len1);
- vector<int> y2=counting_vector(tree[2*idx+2].v, tree[2*idx+2].d, len2);
- unite(tree[idx].v, y1, y2);
- }
- int counting(vector<int>& ans, int x, int k){
- int cnt=0;
- for (int i=0; i<40; i++){
- if (!((x>>(39-i))&1)){
- cnt+=ans[i]*(1<<(39-i));
- }else{
- cnt+=(1<<(39-i))*(k-ans[i]);
- }
- }
- return cnt;
- }
- int answer(vector<Note>& tree, int idx, int L, int R){
- if (L>=tree[idx].r || R<=tree[idx].l){
- return 0;
- }
- if (L<=tree[idx].l && R>=tree[idx].r){
- int len=tree[idx].r-tree[idx].l;
- return counting(tree[idx].v, tree[idx].d, len);
- }
- push(tree, idx);
- int len1=tree[2*idx+1].r-tree[2*idx+1].l;
- int len2=tree[2*idx+2].r-tree[2*idx+2].l;
- vector<int> y1=counting_vector(tree[2*idx+1].v, tree[2*idx+1].d, len1);
- vector<int> y2=counting_vector(tree[2*idx+2].v, tree[2*idx+2].d, len2);
- unite(tree[idx].v, y1, y2);
- return answer(tree, 2*idx+1, L, R)+answer(tree, 2*idx+2, L, R);
- }
- signed main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin>>n;
- vector<vector<int>> a(n);
- for (int i=0; i<n; i++){
- int q;
- cin>>q;
- a[i]=binary_rep(q);
- }
- int m;
- cin>>m;
- vector<Note> tree(4*n);
- build(tree, 0, 0, n, a);
- while(m--){
- int t;
- cin>>t;
- if (t==1){
- int L, R;
- cin>>L>>R;
- L--;
- cout<<answer(tree, 0, L, R)<<"\n";
- }
- else{
- int L, R, x;
- cin>>L>>R>>x;
- L--;
- change(tree, 0, L, R, x);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement