fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <string.h>
  5. #include <stdarg.h>
  6.  
  7. const double eps=1e-11;
  8. typedef long long ll;
  9. typedef long long int lli;
  10. typedef unsigned long long ull;
  11. typedef long double ld;
  12.  
  13. #define swap(a,b,tmp) { tmp=b; b=a; a=tmp; }
  14. #define foi(i,s,e) for(i=s;i<=e;i++)
  15. #define fod(i,s,e) for(i=s;i=>e;i--)
  16. #define abs(a)(a<0?-(a):a)
  17. #define iin(n) scanf("%d",&n)
  18. #define iout(n) printf("%d",n)
  19. #define sin(s) scanf("%s",&s)
  20. #define sout(s) printf("%s",s)
  21. #define MAX 1000000
  22.  
  23. typedef int T;                  /* type of item to be stored */
  24. #define compLT(a,b) (a < b)
  25. #define compEQ(a,b) (a == b)
  26.  
  27. /* Red-Black tree description */
  28. typedef enum { BLACK, RED } nodeColor;
  29.  
  30. typedef struct Node_ {
  31.     struct Node_ *left;         /* left child */
  32.     struct Node_ *right;        /* right child */
  33.     struct Node_ *parent;       /* parent */
  34.     nodeColor color;            /* node color (BLACK, RED) */
  35.     T data;                     /* data stored in node */
  36. } Node;
  37.  
  38. #define NIL &sentinel           /* all leafs are sentinels */
  39. Node sentinel = { NIL, NIL, 0, BLACK, 0};
  40.  
  41. Node *root = NIL;               /* root of Red-Black tree */
  42.  
  43. void rotateLeft(Node *x) {
  44.  
  45.    /**************************
  46.     *  rotate node x to left *
  47.     **************************/
  48.  
  49.     Node *y = x->right;
  50.  
  51.     /* establish x->right link */
  52.     x->right = y->left;
  53.     if (y->left != NIL) y->left->parent = x;
  54.  
  55.     /* establish y->parent link */
  56.     if (y != NIL) y->parent = x->parent;
  57.     if (x->parent) {
  58.         if (x == x->parent->left)
  59.             x->parent->left = y;
  60.         else
  61.             x->parent->right = y;
  62.     } else {
  63.         root = y;
  64.     }
  65.  
  66.     /* link x and y */
  67.     y->left = x;
  68.     if (x != NIL) x->parent = y;
  69. }
  70.  
  71. void rotateRight(Node *x) {
  72.  
  73.    /****************************
  74.     *  rotate node x to right  *
  75.     ****************************/
  76.  
  77.     Node *y = x->left;
  78.  
  79.     /* establish x->left link */
  80.     x->left = y->right;
  81.     if (y->right != NIL) y->right->parent = x;
  82.  
  83.     /* establish y->parent link */
  84.     if (y != NIL) y->parent = x->parent;
  85.     if (x->parent) {
  86.         if (x == x->parent->right)
  87.             x->parent->right = y;
  88.         else
  89.             x->parent->left = y;
  90.     } else {
  91.         root = y;
  92.     }
  93.  
  94.     /* link x and y */
  95.     y->right = x;
  96.     if (x != NIL) x->parent = y;
  97. }
  98.  
  99. void insertFixup(Node *x) {
  100.  
  101.    /*************************************
  102.     *  maintain Red-Black tree balance  *
  103.     *  after inserting node x           *
  104.     *************************************/
  105.  
  106.     /* check Red-Black properties */
  107.     while (x != root && x->parent->color == RED) {
  108.         /* we have a violation */
  109.         if (x->parent == x->parent->parent->left) {
  110.             Node *y = x->parent->parent->right;
  111.             if (y->color == RED) {
  112.  
  113.                 /* uncle is RED */
  114.                 x->parent->color = BLACK;
  115.                 y->color = BLACK;
  116.                 x->parent->parent->color = RED;
  117.                 x = x->parent->parent;
  118.             } else {
  119.  
  120.                 /* uncle is BLACK */
  121.                 if (x == x->parent->right) {
  122.                     /* make x a left child */
  123.                     x = x->parent;
  124.                     rotateLeft(x);
  125.                 }
  126.  
  127.                 /* recolor and rotate */
  128.                 x->parent->color = BLACK;
  129.                 x->parent->parent->color = RED;
  130.                 rotateRight(x->parent->parent);
  131.             }
  132.         } else {
  133.  
  134.             /* mirror image of above code */
  135.             Node *y = x->parent->parent->left;
  136.             if (y->color == RED) {
  137.  
  138.                 /* uncle is RED */
  139.                 x->parent->color = BLACK;
  140.                 y->color = BLACK;
  141.                 x->parent->parent->color = RED;
  142.                 x = x->parent->parent;
  143.             } else {
  144.  
  145.                 /* uncle is BLACK */
  146.                 if (x == x->parent->left) {
  147.                     x = x->parent;
  148.                     rotateRight(x);
  149.                 }
  150.                 x->parent->color = BLACK;
  151.                 x->parent->parent->color = RED;
  152.                 rotateLeft(x->parent->parent);
  153.             }
  154.         }
  155.     }
  156.     root->color = BLACK;
  157. }
  158.  
  159. Node *insertNode(T data) {
  160.     Node *current, *parent, *x;
  161.  
  162.    /***********************************************
  163.     *  allocate node for data and insert in tree  *
  164.     ***********************************************/
  165.  
  166.     /* find where node belongs */
  167.     current = root;
  168.     parent = 0;
  169.     while (current != NIL) {
  170.         if (compEQ(data, current->data)) return (current);
  171.         parent = current;
  172.         current = compLT(data, current->data) ?
  173.             current->left : current->right;
  174.     }
  175.  
  176.     /* setup new node */
  177.     if ((x = malloc (sizeof(*x))) == 0) {
  178.         printf ("insufficient memory (insertNode)\n");
  179.         exit(1);
  180.     }
  181.     x->data = data;
  182.     x->parent = parent;
  183.     x->left = NIL;
  184.     x->right = NIL;
  185.     x->color = RED;
  186.  
  187.     /* insert node in tree */
  188.     if(parent) {
  189.         if(compLT(data, parent->data))
  190.             parent->left = x;
  191.         else
  192.             parent->right = x;
  193.     } else {
  194.         root = x;
  195.     }
  196.  
  197.     insertFixup(x);
  198.     return(x);
  199. }
  200.  
  201. void scan_int(int *n){
  202.     int tmp=0;
  203.     char ch;
  204.     int len=fread(&ch,sizeof(char),1,stdin);
  205.     while((ch < '0' || ch > '9') && len>0 ) len=fread(&ch,sizeof(char),1, stdin);
  206.     while(  ch >= '0' && ch <= '9' && len>0 ){
  207.             tmp = (tmp<<3)+(tmp<<1) + ch-'0';
  208.             len=fread(&ch,sizeof(char),1, stdin);
  209.             }
  210.            *n=tmp;
  211. }
  212.  
  213. lli modifysum(Node* t,lli *cng,int c,int d)
  214. {
  215.     lli mod=0;
  216.     if(t==NIL) return 0;
  217.     if(t->data>=c&&t->data<=d){
  218.         mod+=cng[t->data];
  219.         if(t->data!=d) mod+=modifysum(t->right,cng,c,d);
  220.         if(t->data!=c) mod+=modifysum(t->left,cng,c,d);
  221.     }else if(t->data<c){
  222.         mod+=modifysum(t->right,cng,c,d);
  223.     }else{
  224.         mod+=modifysum(t->left,cng,c,d);
  225.     }
  226.     return mod;
  227. }
  228.  
  229. int main()
  230. {
  231.     int n,q;
  232.     lli *a;
  233.     a=(lli*)malloc(MAX*sizeof(lli));
  234.     lli *cng;
  235.     cng=(lli*)malloc(MAX*sizeof(lli));
  236.     int *flg;
  237.     flg=(int*)malloc(MAX*sizeof(int));
  238.     fscanf(stdin,"%d",&n);
  239.     fscanf(stdin,"%d",&q);
  240.     int i=0;
  241.     char ch;
  242.     int c,d,tmp2;
  243.     flg[i]=0;
  244.     cng[i]=0;
  245.     fscanf(stdin,"%d",&tmp2);
  246.     a[i]=tmp2; i++;
  247.  
  248.     while(i<n){
  249.         flg[i]=0;
  250.         cng[i]=0;
  251.         scan_int(&tmp2);
  252.         a[i]=tmp2+a[i-1];
  253.         i++;
  254.     }
  255.     lli sum,tp;
  256.     while(q--){
  257.         ch='@';
  258.         sum=0;
  259.         while(ch!='S'&&ch!='T'&&ch!='G') fread(&ch,sizeof(char),1,stdin);
  260.         scan_int(&c); scan_int(&d);
  261.         if(ch=='S'){
  262.             if(c==0) sum=a[d];
  263.             else sum=a[d]-a[c-1];
  264.             tp=modifysum(root,cng,c,d);
  265.             sum+=tp;
  266.             fprintf(stdout,"%lld\n",sum);
  267.         }else if(ch=='G'){
  268.             cng[c]+=d;
  269.             if(flg[c]!=1){ insertNode(c); flg[c]=1; }
  270.         }else{
  271.             cng[c]-=d;
  272.             if(flg[c]!=1){ insertNode(c); flg[c]=1; }
  273.         }
  274.     }
  275.  
  276.     return 0;
  277. }
Success #stdin #stdout 0s 21968KB
comments (?)
stdin
copy 
5 3
1000 1002 1003 1004 1005
S 0 2
G 0 3
S 0 2
stdout
copy 
3005
3008
https://ideone.com/nQpx7n
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!