題目描述

You are a denizen of Linetopia, whose n major cities happen to be equally spaced along an east-west line. In?fact, they are often numbered in order from 1 to n, where 1 is the westmost city and n is the eastmost city.?
Linetopia was a lovely place to live until forces from neighboring Trapez invaded. As part of Linetopia’s?Shielding Lives and Protecting Citizens initiative, you have been called upon to process information about?Trapezoid troop movements so we can determine which cities have been hardest hit and know where to send?reinforcements.
Linetopia intelligence has discovered that the Trapezoid forces are attacking in the following pattern. They?are sending massive aircraft to drop troops on Linetopia cities. Each aircraft starts at some city i, dropping?s soldiers. The aircraft then proceeds to ?y either east or west. Each time it ?ies over another city, it drops?a more soldiers than it dropped on the previous city it passed. After performing d drops, the aircraft returns?to Trapez to resupply.
You will be receiving intel updates that inform you of the specs of each Trapezoid aircraft passing over?Linetopia. You want to answer queries that ask how many Trapezoid troops have been dropped on a?particular city. Are you up to the task?

?

輸入

The first line of input contains a single integer T (1 ≤ T ≤ 10), the number of test cases. The first line?of each test case contains two integers: m (1 ≤ m ≤ 10,000), the number of updates and queries and n?(1 ≤ n ≤ 500,000), the number of cities in Linetopia.
The next m lines of input are either updates or queries. Update lines begin with a capital U, then contain?either a capital E (east) or W (west) to indicate direction, and then contain four integers i (1 ≤ i ≤ n), s?(1 ≤ s ≤ 10,000), a (0 ≤ a ≤ 10,000), and d (1 ≤ d ≤ n). These integers signify the starting city, the starting?number of soldiers, the increase in soldiers per city, and the number of drops, respectively. You can assume?d never results in an aircraft flying to the west of city 1 or to the east of city n.
Query lines begin with a capital Q, and then contain a single integer i (1 ≤ i ≤ n) indicating the city being?queried.

?

輸出

For each query in the input, output a single line containing the number of Trapezoid troops dropped in that?city.

?

樣例輸入

復制樣例數據

1
8 3
U E 1 5 2 3
Q 1
Q 2
Q 3
U W 3 10 10 2
Q 1
Q 2
Q 3

樣例輸出

5
7
9
5
27
19

?

提示

Two aircrafts fly over Linetopia. The first starts at city 1 and heads east. It drops 5 soldiers on city 1, 7
soldiers on city 2, and 9 soldiers on city 3. The second starts at city 3 and flies west. It drops 10 soldiers on
city 3 and 20 soldiers on city 2.

?

題目大意：

先輸入一個整數t，代表有t組測試樣例，對于每組樣例先輸入兩個整數m,n，m代表下面m行操作，n代表數組的長度，對于每一行操作，先輸入一個字母，'U'代表修改，‘Q’代表查詢，對于U操作，先輸入一個字母,'E'代表向右，'W'代表向左，后面跟著四個正整數a,b,c,d，代表從數組里面的第a項開始，往左或往右修改d項，對于第一項將其加上b,第二項加上b+c，第三項加上b+2*c，等等，按照等差的形式修改這d項元素。而Q操作即查詢經過修改后的元素是多少。

解題思路：

此題只需將所有的修改操作存在一個結構體中，當進行查詢時，通過遍歷這些操作，判斷所需要查詢的元素是否在其修改區間內，在就改變元素的值，否則繼續。注意：此題需用scanf,printf輸入輸出，用cin,cout會超時，并且數據類型最好定義為long long，防止出錯。

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
struct node
{char dir;int start;ll fir;ll d;int len;
}arr[500500];
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;scanf("%d",&t);while(t--) {char s1[10];char s[10];int cnt=0;int m,n;scanf("%d %d",&m,&n);while(m--) {scanf("%s",s1);if(s1[0]=='U') {scanf("%s",s);int a,d;ll b,c;scanf("%d %lld %lld %d",&a,&b,&c,&d);cnt++;arr[cnt].dir=s[0];arr[cnt].start=a;arr[cnt].fir=b;arr[cnt].d=c;arr[cnt].len=d;}else {int id;scanf("%d",&id);ll ans=0;for(int i=1;i<=cnt;i++) {if(arr[i].dir=='E') {if(arr[i].start<=id&&arr[i].start+arr[i].len-1>=id) {ans=ans+(arr[i].fir+(id-arr[i].start)*arr[i].d);}}else if(arr[i].dir=='W') {if(arr[i].start>=id&&arr[i].start-arr[i].len+1<=id) {ans=ans+(arr[i].fir+(arr[i].start-id)*arr[i].d);}}}printf("%lld\n",ans);}}}return 0;
}

?