Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<assert.h>
- #define infile "aib.in"
- #define outfile "aib.out"
- #define nmax 200000
- int arb[nmax]; //aici vom salva arborele de intervale
- int n; //numarul de elemente
- int poz,val; //le vom volosi la adaugarea in arbore
- int a,b; //interalul pe care se cauta suma la un query pe un interval
- void add(int rad, int st, int dr)
- {
- if(st==dr) { arb[rad]+=val; return; } //adaugam valoarea la pozitie
- int mij=(st+dr)>>1;
- arb[rad]=0;
- if(poz<=mij && (rad<<1)<nmax) add(rad<<1,st,mij);
- if(mij<poz && ((rad<<1)|1)<nmax) add((rad<<1)|1,mij+1,dr);
- if((rad<<1)<nmax) arb[rad]+=arb[rad<<1];
- if(((rad<<1)|1)<nmax) arb[rad]+=arb[(rad<<1)|1];
- }
- int query(int rad, int st, int dr)
- {
- if(a<=st && dr<=b) return arb[rad]; //suma
- int mij=(st+dr)>>1;
- int sum=0;
- if(a<=mij && (rad<<1)<nmax) sum+=query(rad<<1,st,mij);
- if(mij<b && ((rad<<1)|1)<nmax) sum+=query((rad<<1)|1,mij+1,dr);
- return sum;
- }
- int query2(int rad, int st, int dr, int sum)
- {
- if(arb[rad]==sum) return dr-st+1; //numarul de elemente ale acestui subarbore
- if(arb[rad]<sum || st==dr) return -1; //nu se poate obtine
- int mij=(st+dr)>>1;
- if((rad<<1)<nmax && sum<=arb[rad<<1]) return query2(rad<<1,st,mij,sum);
- else if(((rad<<1)|1)<nmax)
- {
- int x=query2((rad<<1)|1,mij+1,dr,sum-arb[rad<<1]);
- if(x<0) return -1;
- return mij-st+1+x;
- }
- else return -1;
- }
- int main()
- {
- int t,u;
- freopen(infile,"r",stdin);
- freopen(outfile,"w",stdout);
- scanf("%d %d\n",&n,&t);
- //citim sirul initial
- for(poz=1;poz<=n;poz++)
- {
- scanf("%d",&val);
- add(1,1,n);
- }
- //executam operatiile
- int check = 1;
- while(t--)
- {
- scanf("%d ",&u); //tipul operatiei
- assert(u == 1);
- if(!u)
- { //daca avem modificarea unei valori
- scanf("%d %d\n",&poz,&val);
- add(1,1,n);
- }
- else if(u==1)
- { //suma unui interval
- scanf("%d %d\n",&a,&b);
- assert(a == check);
- assert(b == check);
- printf("%d\n",query(1,1,n));
- }
- else if(u==2)
- { //pozitia pentru obtinerea sumei
- scanf("%d\n",&val);
- printf("%d\n",query2(1,1,n,val));
- }
- check++;
- }
- fclose(stdin);
- fclose(stdout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement