A -- A simple math problem

Time Limit：2s Memory Limit：128MByte

Submissions：1599Solved：270

DESCRIPTION

You have a sequence ${\mathrm{anan,\; which\; satisfies:}}^{}$

Now you should find the value of $\lfloor 10an\rfloor \lfloor 10an\rfloor .$

INPUT

The input includes multiple test cases. The number of test case is less than 1000. Each test case contains only one integer

$\mathrm{n(1\le n\le 109)n(1\le n\le 109)。}$

OUTPUT

For each test case, print a line of one number which means the answer.

SAMPLE INPUT

5

20

1314

SAMPLE OUTPUT

5

21

1317

这个题就是找规律啊，一个很明显的规律是每一项都有一个贡献，但是这个范需要自己找，10的话按照log是要加1结果不需要，入手点就是这里，看看哪些少加了1，每个数量级多一个，这个pow损精度，wa了好几次，主要是n==1时输出值也是1，这个才是我被坑的最严重的

以下是题解

#include 
         
          #include 
          
           int pow10(int i){int ans=1;for(int j=0;j
          
         

B - Buildings

Time Limit：2s Memory Limit：128MByte

Submissions：699Solved：186

DESCRIPTION

There are $\mathrm{nn\; buildings\; lined\; up,\; and\; the\; height\; of\; the\; ii-th\; house\; is\; hihi.}$

An inteval $[l,r][l,r](l\le r)(l\le r)\; is\; harmonious\; if\; and\; only\; if\; max(hl,\dots ,hr)-min(hl,\dots ,hr)\le kmax(hl,\dots ,hr)-min(hl,\dots ,hr)\le k.$

Now you need to calculate the number of harmonious intevals.

INPUT

The first line contains two integers

$\mathrm{n(1\le n\le 2\times 105),k(0\le k\le 109)n(1\le n\le 2\times 105),k(0\le k\le 109).\; The\; second\; line\; contains\; nn\; integers\; hi(1\le hi\le 109)hi(1\le hi\le 109).}$

OUTPUT

Print a line of one number which means the answer.

SAMPLE INPUT

3 1 1 2 3

SAMPLE OUTPUT

5

HINT

Harmonious intervals are:

$[1,1],[2,2],[3,3],[1,2],[2,3][1,1],[2,2],[3,3],[1,2],[2,3].$

$模板题？？？区间最大值最小值的差小于等于k的值有多少组，单调栈，RMQ都不会被卡的$

#include 
            
             #define LL long longusing namespace std;const int maxN = 2e5+10;int n, k, a[maxN];LL ans;void input() {    scanf("%d%d", &n, &k);    for (int i = 0; i < n; ++i)        scanf("%d", &a[i]);}void work() {    ans = 0;    deque
             
               mi, ma;    int p = 0;    for (int i = 0; i < n; ++i) {        while (!(mi.empty() && ma.empty()) &&                !(abs(a[i]-a[mi.front()]) <= k && abs(a[i]-a[ma.front()]) <= k)) {            p++;            while (!mi.empty() && mi.front() < p)                mi.pop_front();            while (!ma.empty() && ma.front() < p)                ma.pop_front();        }        ans += i-p+1;        while (!mi.empty() && a[mi.back()] > a[i])            mi.pop_back();        mi.push_back(i);        while (!ma.empty() && a[ma.back()] < a[i])            ma.pop_back();        ma.push_back(i);    }    printf("%lld\n", ans);}int main() {    input();    work();    return 0;}
             
            

 ST表

void rmqinit()  {      for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = w[i];      int m = (int)(log(n * 1.0) / log(2.0));      for(int i = 1; i <= m; i++)          for(int j = 1; j <= n; j++)          {              mx[j][i] = mx[j][i - 1];              if(j + (1 << (i - 1)) <= n) mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);              mi[j][i] = mi[j][i - 1];              if(j + (1 << (i - 1)) <= n) mi[j][i] = min(mi[j][i], mi[j + (1 << (i - 1))][i - 1]);          }  }  int rmqmin(int l,int r)  {      int m = (int)(log((r - l + 1) * 1.0) / log(2.0));      return min(mi[l][m] , mi[r - (1 << m) + 1][m]);  }  int rmqmax(int l,int r)  {      int m = (int)(log((r - l + 1) * 1.0) / log(2.0));      return max(mx[l][m] , mx[r - (1 << m) + 1][m]);  }