#include using namespace std; #define F(i,L,U) for ((i) = (L); (i) < (U); (i)++) #define FE(i,L,U) for ((i) = (L); (i) <= (U); (i)++) #define LINE(line) fgets(line, sizeof(line), stdin) #define CLR(a) memset(a, 0,sizeof(a)) #define LSOne(S) (S & (-S)) #define MAX_N 100005 #define LOG_TWO_N 30 #define MAX(a, b) (((a) > (b)) ? (a) : (b)) int _A[MAX_N]; int SpT[MAX_N][LOG_TWO_N]; int _A2[MAX_N]; int SpT2[MAX_N][LOG_TWO_N]; long times[MAX_N]; long vals[MAX_N]; vector ft; class FT{ private: public: FT(){} FT(int n) {ft.assign(n+1, 0);} long rsq(int b) { long sum = 0; for(; b; b -= LSOne(b)) sum += ft[b]; return sum; } long rsq(int a, int b) { return rsq(b) - (a==1? 0 : rsq(a-1)); } void adjust(int k, long v) { for(; k < (int) ft.size(); k += LSOne(k)) { ft[k] += v; //~ printf("k=%d\n", k); } } }; class RMiQ{ //~ private: //~ int _A[MAX_N]; //~ int SpT[MAX_N][LOG_TWO_N]; public: RMiQ(int n) { int i, j; //~ _A.resize(MAX_N); //~ fill(_A.begin(), _A.end(), 0); F(i,0,n){ _A[i] = vals[i+1]; SpT[i][0] = i; } for(j = 1; (1< _A2[SpT2[ i + (1 << (j-1))][j-1] ]){ SpT2[i][j] = SpT2[i][j-1]; }else{ SpT2[i][j] = SpT2[i + (1 << (j-1))][j-1]; } } } } long query(int i, int j) { int k = (int)floor(log((double)j - i+1) / log(2.0)); if (_A2[SpT2[i][k]] <= _A2[SpT2[j - (1< res) counter++; } else if (strcmp(ope, "lt") == 0){ if (vals[i] < res) counter++; } } }else if (strcmp(fun, "max") == 0){ FE(i,2,N){ //~ printf("for vals[%d]=%d at times[%d] = %d\n", i, vals[i], i, times[i]); long newTime = MAX(0, times[i] - L_i); long newTime_i = lower_bound(×[0], ×[N], newTime) - times; long res = 0; //~ printf("new time = %d, new time i =%d\n", newTime, newTime_i); int nn = i - newTime_i; if (nn == 0) continue; res = vals[mini.query(newTime_i, i-1)+1]; //~ printf("max=%d < val=%d\n\n", res, vals[i]); if (strcmp(ope, "gt") == 0){ if (vals[i] > res) counter++; } else if (strcmp(ope, "lt") == 0){ if (vals[i] < res) counter++; } } }else if (strcmp(fun, "avg") == 0){ //~ printf("rsq %d\n", ft.rsq(1, 10)); FE(i,2,N){ //~ printf("for vals[%d]=%d at times[%d] = %d\n", i, vals[i], i, times[i]); long newTime = MAX(0, times[i] - L_i); long newTime_i = lower_bound(×[0], ×[N], newTime) - times; double res = 0; //~ printf("new time = %d, new time i =%d\n", newTime, newTime_i); int nn = i - newTime_i; if (nn == 0) continue; res = ft.rsq(newTime_i, i-1) / (double)(nn); //~ printf("res=%lf < val=%d\n\n", res, vals[i]); if (strcmp(ope, "gt") == 0){ if (vals[i] > res) counter++; } else if (strcmp(ope, "lt") == 0){ if (vals[i] < res) counter++; } } } printf("%ld\n", counter); } } return 0; }