According to the meaning of the three questions in this exam, they are all template questions, T1 monotonous queue template, T2 digital DP template, T3 line segment tree template. But because the first two templates are not familiar with each other, they dare not write in the exam, and the line segment tree is also written and exploded, and finally only 50 points.

T1:
Title Description:
On an array of n elements, a window of length k slides from left to right. Every time the window slides to a position, we can see k elements in the window. As shown in the following example, suppose the array is [13-1-3,536 7], and k equals 3:

Input format
The first line of input consists of two integers n, k, n for the length of the array, and K for the length of the window.
The next line contains n integers, representing an array of n elements.

Output format
The output consists of two lines, each containing n-k+1 integer.
The first line represents the minimum value of the window sliding from left to right.
The second line represents the maximum value of the window as it slides from left to right.

Remarks
[Data Scope]
For 100% of the data, 3 <= n <= 1000000, 1 <= K <= n, each element in the array is in the range of int.

Topic: Select the number of k at a time, and count the maximum and minimum. So when I couldn't type out the positive solution, I thought of the interval query of the line segment tree and barely got 50 points. DZY is also the line segment tree, but A, I can't help it.

Positive Solution: Maintain two monotonous queues, which contain subscripts to the minimum and maximum values, one is to maintain the minimum, and the other is to maintain the maximum. Every time a new number is pushed into the end of the queue, first consider maintaining the minimum queue. If the number in front is larger than that in front, it means that these numbers can not contribute to the answer, then direct r - (the number of the end of the queue), move it forward, and the maximum value is the same.

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<cctype>
using namespace std;
const int N =1e6+5;
int n,k,q1[N],q2[N],a[N],ans1[N],ans2[N],buf[1000];
//---------------------
inline int Readint()
{
    int i=0,f=1; char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) i=(i<<1)+(i<<3)+ch-'0';
    return i*f;
}
//---------------------
inline void W(int x) //Because the data is large, the output is optimized.
{
    if(!x){putchar('0');return;}
    if(x<0){putchar('-');x=-x;}
    while(x)buf[++buf[0]]=x%10,x/=10;
    while(buf[0])putchar('0'+buf[buf[0]--]);
}
//---------------------
int main()
{
    freopen("window.in","r",stdin);
    //freopen("window.out","w",stdout);

    n=Readint(),k=Readint();
    for(int i=1;i<=n;i++) a[i]=Readint();
    int l1=0,l2=0,r1=1,r2=1;
    for(int i=1;i<=n;i++){
        while(l1<=r1 && q1[l1]<=i-k) l1++; //Minimum queue
        while(l2<=r2 && q2[l2]<=i-k) l2++; //Maximum queue 
        while(l1<=r1 && a[i]<=a[q1[r1]]) r1--; //He has been decreasing since he was younger.
        q1[++r1]=i;
        while(l2<=r2 && a[i]>=a[q2[r2]]) r2--; //He's been losing since he was older.
        q2[++r2]=i;
        ans1[i]=a[q1[l1]];
        ans2[i]=a[q2[l2]];
    }
    for(int i=k;i<=n;i++) W(ans1[i]),putchar(' ');
    cout<<endl;
    for(int i=k;i<=n;i++) W(ans2[i]),putchar(' ');
    return 0;
}

T2: Nude Digital DP
Title Description:
CLC NOIP2015 kneels sadly. He vaguely remembers that his admission number is 37 (actually false). Now CLC will face another competition. He hopes that the admission number will not appear 37 (continuous). At the same time, he hates 4 very much, so he does not want 4 to appear in the admission number. Now he wants to know how many valid admission numbers there are between A and B.

Digital Dp is not explained

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iomanip>
#include<iostream>
#include<cmath>
#include<ctime>
#include<cctype>
using namespace std;
int x,y,a[20],dp[20][2];
//---------------------
inline int Readint()
{
    int i=0,f=1; char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) i=(i<<1)+(i<<3)+ch-'0';
    return i*f;
}
//---------------------
/*
pos In order to determine whether sta is the current state and whether sta is the current state, limit is used to determine whether the maximum number of digits can be enumerated to 9.
*/
//---------------------
inline int dfs(int pos,int pre,int sta,int limit) 
{
    if(pos==-1) return 1;
    if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
    int up= limit ? a[pos] : 9;
    int tmp=0;
    for(int i=0;i<=up;i++){
        if(pre==3 && i==7) continue;
        if(i==4) continue;
        tmp+=dfs(pos-1,i,i==3,limit && i==a[pos]);
    }
    if(!limit) dp[pos][sta]=tmp;
    return tmp;
}
//---------------------
inline int solve(int x)
{
    int pos=0;
    while(x) //Calculate each digit
    {
        a[pos++]=x%10;
        x=x/10;
    }
    return dfs(pos-1,-1,0,true);
}
//---------------------
int main()
{
    x=Readint(),y=Readint();
    memset(dp,-1,sizeof(dp));
    cout<<solve(y)-solve(x-1); //Statistical subtraction of [0,y] and [0,x-1]
    return 0;
}

T3:
Title Description:
The wicked big head appears again! He's playing a game of mental retardation: playing monsters.

Now there is a row of monsters on the big head screen. Each big head has a blood strip on its head. Each big head can choose an interval to attack. The attack value is K. The monster whose blood volume is less than K in this interval will be killed mercilessly by the big head. Of course, the monster will not wait to die. For the monster in a certain interval, they will add X at the same time.

Although the head is big, IQ is not very high, and all the players here don't know where they are taller than him. At this time, the big head made a big trick - cheater, but the big head cheater is not high-level can only choose the interval of 7 times the blood of the monster to kill, ask: How many monsters can he kill?

Input format
The first line has a positive integer n;
Next n rows of n integers;
Next, a positive integer Q denotes the number of operations.
Next, line Q has several integers per line. If the first number is add, followed by three positive integers a,b, X, it means that each number in the interval [a,b] increases X, and if it is count, it means the number of statistical intervals [a,b] that can be divided by 7 integers.

Positive Solution: Mark the segment tree, count the number of 0,1,2,3,4,5,6 modular sum of the value and 7 in each interval, and use only the number of the remainder of the summer stimulation to be 0 at last.

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<cctype>
using namespace std;
const int N = 1e5+5;
int a[N],n,m,x,y,z,num;
int sum[N<<2][10],add[N<<2],tmp[10];
char s[10];
//---------------------
inline int Readint()
{
    int i=0,f=1; char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) i=(i<<1)+(i<<3)+ch-'0';
    return i*f;
}
//---------------------
inline void update(int root)
{
    for(int i=0;i<=6;i++)
      sum[root][i]=sum[root<<1][i]+sum[root<<1|1][i];
}
//---------------------
inline void mode(int k,int x)
{
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<=6;i++) tmp[i]=sum[k][i];
    for(int i=0;i<=6;i++) sum[k][(i+x)%7]=tmp[i];
}
//---------------------
void Pushdown(int k)
{
    if(add[k])
    {
        add[k<<1]=(add[k<<1]+add[k])%7,mode(k<<1,add[k]);
        add[k<<1|1]=(add[k<<1|1]+add[k])%7,mode(k<<1|1,add[k]);
        add[k]=0;
    }
}
//---------------------
void build(int k,int l,int r)
{
    if(l==r)
    {
        sum[k][a[l]]++;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    update(k);
}
//---------------------
void modify(int k,int l,int r,int x,int y,int v)
{
    if(x<=l&&r<=y)
    {
        memset(tmp,0,sizeof(tmp));
        mode(k,v);
        add[k]=(add[k]+v)%7;
        return;
    }
    Pushdown(k);
    int mid=l+r>>1;
    if(y<=mid)modify(k<<1,l,mid,x,y,v);
    else if(x>mid)modify(k<<1|1,mid+1,r,x,y,v);
    else modify(k<<1,l,mid,x,mid,v),modify(k<<1|1,mid+1,r,mid+1,y,v);
    update(k);
}
//---------------------
inline int Query(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return sum[k][0];
    Pushdown(k);
    int mid=(l+r)>>1;
    if(y<=mid)  return Query(k<<1,l,mid,x,y);
    else if(x>mid) return Query(k<<1|1,mid+1,r,x,y);
    else return Query(k<<1,l,mid,x,y)+Query(k<<1|1,mid+1,r,x,y);
}
//---------------------
int main()
{
    freopen("seg.in","r",stdin);
    //freopen("seg.out","w",stdout);

    n=Readint();
    for(int i=1;i<=n;i++) a[i]=Readint()%7;
    build(1,1,n);
    m=Readint();
    for(int i=1;i<=m;i++){
        scanf("%s",s);
        if(s[0]=='a'){
            x=Readint(),y=Readint(),z=Readint()%7;
            modify(1,1,n,x,y,z);
        }
        if(s[0]=='c') {
            x=Readint(),y=Readint();
            cout<<Query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}