fork download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3. #ifndef ONLINE_JUDGE
  4. #define get getchar
  5. #else
  6. #define get getchar_unlocked
  7. #endif
  8. inline int scan_f()
  9. {
  10. 	int n=0,s=1;
  11. 	char p=get();
  12. 	if(p=='-')
  13. 		s=-1;
  14. 	while((p<'0' || p>'9') && p!=EOF && p!='-')
  15. 		p=get();
  16. 	if(p=='-')
  17. 		s=-1,p=get();
  18. 	while(p>='0' && p<='9' )
  19. 	{
  20. 		n=(n<<3)+(n<<1)+(p-'0');
  21. 		p=get();
  22. 	}
  23. 	return (n*s);
  24. }
  25. #define max_size 1000005
  26.  
  27. typedef long long int lli;
  28.  
  29. struct seg_t{
  30. lli c,h,e,f,ch,ce,cf,hc,ec,fc,he,hf,eh,fh,ef,fe;
  31. };
  32. char s[1000005];
  33. struct seg_t tree[4*max_size];
  34.  
  35. void construct( int node, int i, int j )
  36. {
  37. 	    if(i==j)
  38.     	{
  39.     		tree[node]=((struct seg_t) { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0});
  40.     		if(s[i]=='c')
  41.     		tree[node].c++;
  42.     		else if(s[i]=='h')
  43.     		tree[node].h++;
  44.     		else if(s[i]=='e')
  45.     		tree[node].e++;
  46.     		else if(s[i]=='f')
  47.     		tree[node].f++;
  48.     	}
  49.     	else
  50.     	{
  51.     		construct( node*2, i , (i + j)/2);
  52.     		construct( node*2+1, (i+j)/2 + 1, j);
  53.     		struct seg_t left = tree[node*2];
  54.     		struct seg_t right = tree[node*2+1];
  55.     		tree[node].c=left.c+right.c;
  56.     		tree[node].h=left.h+right.h;
  57.     		tree[node].e=left.e+right.e;
  58.     		tree[node].f=left.f+right.f;
  59.     		tree[node].ch+=(left.c*right.h) + left.ch + right.ch;
  60.     		tree[node].ce+=(left.c*right.e) + left.ce + right.ce;
  61.     		tree[node].cf+=(left.c*right.f) + left.cf + right.cf;
  62.     		tree[node].hc+=(left.h*right.c) + left.hc + right.hc;
  63.     		tree[node].ec+=(left.e*right.c) + left.ec + right.ec;
  64.     		tree[node].fc+=(left.f*right.c) + left.fc + right.fc;
  65.     		tree[node].he+=(left.h*right.e) + left.he + right.he;
  66.     		tree[node].hf+=(left.h*right.f) + left.hf + right.hf;
  67.     		tree[node].eh+=(left.e*right.h) + left.eh + right.eh; 
  68.     		tree[node].fh+=(left.f*right.h) + left.fh + right.fh;
  69.     		tree[node].ef+=(left.e*right.f) + left.ef + right.ef;
  70.     		tree[node].fe+=(left.f*right.e) + left.fe + right.fe;
  71.     	}
  72. }
  73.  
  74. struct seg_t query(int node, int a, int b, int i, int j)
  75. {
  76.     if( a==i && b==j)
  77.     return tree[node];
  78.     else if ( j <= ( a + b ) / 2 ) {
  79.     return query( node * 2, a, ( a + b ) / 2, i, j );
  80.     }
  81.     if ( i > ( a + b ) / 2 ) {
  82.     return query( node * 2 + 1, ( a + b ) / 2 + 1, b, i, j );
  83.     }
  84.     struct seg_t left = query( node * 2, a, ( a + b ) / 2, i, ( a + b ) / 2 );
  85.     struct seg_t right = query( node * 2 + 1, ( a + b ) / 2 + 1, b, ( a + b ) / 2 + 1, j );
  86.     struct seg_t ans;
  87.     ans.c=left.c+right.c;
  88.     ans.h=left.h+right.h;
  89.     ans.e=left.e+right.e;
  90.    	ans.f=left.f+right.f;
  91.     ans.ch+=(left.c*right.h) + left.ch + right.ch;
  92.     ans.ce+=(left.c*right.e) + left.ce + right.ce;
  93.     ans.cf+=(left.c*right.f) + left.cf + right.cf;
  94.     ans.hc+=(left.h*right.c) + left.hc + right.hc;
  95.     ans.ec+=(left.e*right.c) + left.ec + right.ec;
  96.     ans.fc+=(left.f*right.c) + left.fc + right.fc;
  97.     ans.he+=(left.h*right.e) + left.he + right.he;
  98.     ans.hf+=(left.h*right.f) + left.hf + right.hf;
  99.     ans.eh+=(left.e*right.h) + left.eh + right.eh; 
  100.     ans.fh+=(left.f*right.h) + left.fh + right.fh;
  101.     ans.ef+=(left.e*right.f) + left.ef + right.ef;
  102.     ans.fe+=(left.f*right.e) + left.fe + right.fe;
  103.     return ans;
  104. }
  105.  
  106.  
  107. main()
  108. {
  109. 	scanf("%s",&s);
  110.     int q,l,i,x,y;
  111. 	lli ans;
  112.     l=strlen(s);
  113.     char a,b;
  114.     construct(1,0,l-1);
  115.     /*for(i=1;i<10;i++)
  116.     {
  117.     printf("%d %d %d %d %d %d %d %d %d %d %d %d\n",tree[i].c,tree[i].h,tree[i].e,tree[i].f,tree[i].ch,tree[i].ce,tree[i].cf,tree[i].hc,tree[i].ec,tree[i].fc,tree[i].he,tree[i].hf);
  118.     }*/
  119.     q=scan_f();
  120.     for(i=0;i<q;i++)
  121.     {
  122.     scanf(" %c %c",&a,&b);
  123.     x=scan_f();
  124.     y=scan_f();
  125.     //printf("%c %c %d %d\n",a,b,x,y);
  126.     struct seg_t q=query(1,0,l-1,x-1,y-1);
  127.     if(a=='c' && b=='h')
  128.     ans=q.ch;
  129.     else if(a=='c' && b=='e')
  130.     ans=q.ce;
  131.     else if(a=='c' && b=='f')
  132.     ans=q.cf;
  133.     else if(a=='h' && b=='c')
  134.     ans=q.hc;
  135.     else if(a=='e' && b=='c')
  136.     ans=q.ec;
  137.     else if(a=='f' && b=='c')
  138.     ans=q.fc;
  139.     else if(a=='h' && b=='e')
  140.     ans=q.he;
  141.     else if(a=='h' && b=='f')
  142.     ans=q.hf;
  143.     else if(a=='e' && b=='h')
  144.     ans=q.eh;
  145.     else if(a=='f' && b=='h')
  146.     ans=q.fh;
  147.     else if(a=='e' && b=='f')
  148.     ans=q.ef;
  149.     else if(a=='f' && b=='e')
  150.     ans=q.fe;
  151.     printf("%lld\n",ans);
  152.     }
  153.     return 0;
  154. }
Runtime error #stdin #stdout 0s 511104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/62RGET
language:
C (gcc 8.3)
created:
9 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!